Necessary Conditions for Existence of Skolem Sequence

From ProofWiki
Jump to navigation Jump to search

Theorem

A Skolem sequence of order $n$ can only exist if $n \equiv 0, 1 \pmod 4$.


Proof

Let $S$ be a Skolem sequence of order $n$.

Let $a_i$ and $b_i$ be the positions of the first and second occurrences respectively of the integer $i$ in $S$, where $1 \le i \le n$.

We can thus conclude that:

$b_i - a_i = i$

for each $i$ from 1 to $n$.

Summing both sides of this equation we obtain:

$\ds \sum_i^n b_i - \sum_i^n a_i = \sum_i^n i = \frac {n \paren {n + 1} } 2$

Now the $a_i$ and the $b_i$ represent the positions in the sequence from $1$ to $2 n$.

Hence:

$\ds \sum_i^n b_i + \sum_i^n a_i = \frac {2 n \paren {2 n + 1} } 2 = n \paren {2 n + 1}$

Summing the previous two equations we obtain the identity:

$\ds \sum_i^n b_i = \frac {n \paren {5 n + 3} } 4$

The left hand side of this last equality is a sum of positions and thus must be an integer.

We conclude that the right hand side must also be an integer.

This occurs exactly when: $n \equiv 0, 1 \pmod 4$

$\blacksquare$


Sources

  • 1957: Th. SkolemOn certain distributions of integers in pairs with given differences (Math. Scand. Vol. 5: pp. 57 – 68)