Experimental results
To return to the main Polymath5 page, click here.
The first 1124-sequence with discrepancy 2.
Another sequence of length 1124
Here is another sequence of length [math]\displaystyle{ 1124 }[/math]:
0 + + - - + + - + - - + - - - + + - + - - + + + - + - - + - + + - - + - + - - + + + - + - - + - + + - - + + - + - + + - - + - + + - + - - - + + - - + + + - - + - + - - + + - - + - + + - + - - - + + - + + + - - - + - + + - + - - - + + + - + + - + - - - - + + + + - - + - - - + + - + + - + + - + - + - - + - - - + + + + - - - - + + + - - + - + + - + - - + + - + - - + - + - + - - + + - - + + - - + + - + + - + + - - - - + - + + - + + - - + + - + - - + + + - + - - + - - - + + - - + + - + + - + - - + + - + - - + - - + + - + + + - - - + + - - + + + - - + - + - - - + + - + - - + + - + - - + + + + - - + - - + + - - - + + + - - + - + + - + - - + - - + + - + - - + + - + + - + - + + - - + - - + + - - + - + + - + - - + + + - - + - - - + + - + + - + - - + + - + + - + - - - + - + - - + - + + - - + + + - - - + + - + - - + - + + + - - + - + + - + + - + - - + - - + + - + - + + - + - + - + - - + - - + + - + + - + - - + + - - + - - - + + + - - - + + - - + + - + + + - - - + + - + - + + - - - + - + - - + - + + + - - + - + - - + + - + + - + - - + + - + - + - - + - + - + + - + - - + - - + + + - + - - + + + - - + - - + + - + + - + - - + + - + - - + - - + + - + - - + - - + + - + + + - - - + + - + - - + + - + + - + - - + - - + + - + + - + - - + + - + - - + - - + + - + - - + - - + + - + + - - - + + + - + + - + - - - - + + - - + - + + + - + + - + - - + + - + - - + - - + + - + - - + + - - + - + + - + - - + + - - + - + - - + + + + - - + - - + - - + + - + - - + + - + + - + - - + + - + - + + - - - + - + + - + - - + + - + - + + - - - + + + - - + - - + + - - + - + - - + + - + + - + + - + - - + - + + - - - + - + + - + - - + + - + - - + + - + + - + - - - - + + + - + + - + - - + + - + - - + - - + + - + - - + - - + + - + + - + - - + + - + + - + - - + + - - - - + - + + - - + + + + - - - + - + + - + - - + + - + - - + - - + + - + + - + - - + + + - - + + - - + + - + - - + - - - + + + + - + - - - + - + + - + - - + + - + - + + - - - + + - + + - - - + + - + - + + - - - + - + + + - - - + + - + + - + - - + + - - - - + - + + + - + - - + - - + + - + + - - - + + + - + + - + - - - + - + - - + - + + + - + + - - - - + + + + - - - + - + - - + - + + + + - - - + + - + - - + + - + - + + - - + + - + - - - - + + + + - + - + - - + - - + + - + + - - + - + + - + - - + - + +
The sequence divided into groups of 24, and also with multiples of 8 only.
Varying the upper and lower bounds
If [math]\displaystyle{ N(a,b) }[/math] is the maximum length of a [math]\displaystyle{ \pm 1 }[/math] sequence with the partial sums along its HAPs bounded below by [math]\displaystyle{ -a }[/math] and above by [math]\displaystyle{ b }[/math], then:
[math]\displaystyle{ N(a, b) = N(b, a) }[/math]
[math]\displaystyle{ N(0, b) = b }[/math] (everything must be [math]\displaystyle{ +1 }[/math])
[math]\displaystyle{ N(1, 1) = 11 }[/math] (there are [math]\displaystyle{ 4 }[/math] such sequences: choose [math]\displaystyle{ x_1 }[/math], and use the constraints [math]\displaystyle{ x_n +x_{2n} = 0 }[/math] and [math]\displaystyle{ x_1 + \ldots + x_{2n} = 0 }[/math] to determine the entries up to [math]\displaystyle{ 10 }[/math]; then choose [math]\displaystyle{ x_{11} }[/math])
[math]\displaystyle{ N(1, 2) = 41 }[/math] (there are [math]\displaystyle{ 4 }[/math] such sequences -- example below)
0 + - - + - + + - + + - - + - + + - + - - - + - + + - - + + - + - + + - - - + - + +
[math]\displaystyle{ N(1, 3) = 83 }[/math] (there are [math]\displaystyle{ 216 }[/math] such sequences -- example below)
0 - + - + - + + - + + - - + - + + - - + - - + - + + - + + + - - - + + - + + - - + - + - - + + - - + - + + + - + - - - + + - + - + - - + - + + - + + - - + - + - - - + +
[math]\displaystyle{ N(1, 4) = 131 }[/math] (there are [math]\displaystyle{ 87144 }[/math] such sequences -- example below)
0 + - - + - + + - - + - + + - + + + + - - - + - - + - + + - - + + + - - - + + - + - + - - + + - + + - - + - - + - + + + + - - + - + - - + + + - + - - - - + + - - - + + - - + + + + - - - - + + - + - + + + + - - + + - + - - - + + - - - + - - + + + - + + - - + - - +
[math]\displaystyle{ N(2, 2) \geq 1124 }[/math]
--Alec 13:46, 9 January 2010 (UTC)
Geometric variations
It has been pointed out that the problem can be generalized to higher dimensions, for example by considering sequences with [math]\displaystyle{ \Vert x_n \Vert_2 = 1 }[/math] having partial sums lying within a sphere. It is difficult to do much in the way of computation when the [math]\displaystyle{ x_n }[/math] can vary continuously, but if they are restricted to some finite set the problem becomes purely combinatorial and one can do more.
The seven-point hexagon
If the [math]\displaystyle{ x_n }[/math] are allowed to be any of the six points of a regular hexagon, and one requires all sums along HAPs to be zero or one of those same points, the maximum length of a sequence is [math]\displaystyle{ 116 }[/math]. The following sequence achieves this, where the numbers index the points in order around the hexagon:
-, 0, 3, 3, 0, 3, 0, 2, 4, 0, 1, 4, 3, 1, 5, 0, 2, 4, 3, 1, 5, 5, 1, 4, 1, 2, 5, 3, 2, 5, 4, 1, 4, 1, 2, 5, 0, 2, 4, 4, 1, 5, 2, 1, 4, 3, 1, 5, 5, 2, 4, 1, 2, 4, 0, 1, 5, 4, 1, 4, 2, 2, 4, 0, 1, 5, 4, 2, 5, 1, 2, 4, 3, 1, 5, 5, 1, 4, 1, 3, 4, 2, 1, 0, 4, 1, 4, 3, 1, 5, 0, 2, 4, 5, 2, 4, 1, 1, 5, 3, 2, 0, 3, 4, 5, 1, 1, 3, 4, 1, 5, 0, 2, 4, 1, 3, 5
Here are some of its HAP subseqences, which seem to show the presence of some kind of multiplicative structure, though the structure seems to degenerate as the sequences progress.
The 2-sequence
3, 0, 0, 4, 1, 3, 5, 2, 3, 5, 1, 1, 5, 2, 4, 4, 2, 0, 4, 1, 2, 4, 1, 5, 4, 2, 0, 5, 1, 2, 4, 1, 4, 5, 2, 3, 5, 1, 1, 4, 1, 4, 4, 1, 0, 4, 2, 1, 5, 2, 3, 5, 1, 4, 5, 2, 1, 5
The 3-sequence
3, 0, 0, 3, 0, 3, 5, 1, 3, 4, 1, 0, 4, 2, 3, 5, 1, 0, 4, 2, 0, 4, 1, 3, 5, 1, 2, 4, 3, 0, 5, 1, 3, 3, 1, 4, 0, 1
The 4-sequence
0, 4, 3, 2, 5, 1, 2, 4, 0, 1, 4, 5, 2, 5, 2, 1, 5, 3, 1, 4, 4, 1, 4, 1, 2, 5, 4, 2, 5
The 5-sequence
3, 1, 0, 5, 2, 4, 5, 1, 3, 4, 1, 2, 5, 2, 5, 4, 1, 0, 4, 2, 1, 5, 3
The 6-sequence
0, 3, 3, 1, 4, 0, 2, 5, 0, 2, 4, 3, 1, 4, 0, 1, 3, 4, 1
The 8-sequence
4, 2, 1, 4, 1, 5, 5, 1, 3, 4, 1, 1, 5, 2
The 9-sequence
0, 3, 3, 0, 3, 0, 0, 3, 2, 0, 3, 4
The 10-sequence
1, 5, 4, 1, 4, 2, 2, 4, 0, 2, 5
The 12-sequence
3, 1, 0, 5, 2, 3, 4, 1, 4
The nine-point square
If the [math]\displaystyle{ x_n }[/math] are allowed to be any of the four points [math]\displaystyle{ (\pm 1, 0) }[/math] and [math]\displaystyle{ (0, \pm 1) }[/math], and one requires all sums along HAPs to belong to one of the nine points at unit spacing centred on the origin, the maximum length of a sequence is at least [math]\displaystyle{ 314 }[/math]. The following sequence achieves this:
(1, 0), (0, 1), (-1, 0), (1, 0), (-1, 0), (0, -1), (0, 1), (-1, 0), (1, 0), (1, 0), (0, -1), (-1, 0), (-1, 0), (0, -1), (1, 0), (1, 0), (-1, 0), (0, 1), (1, 0), (-1, 0), (0, -1), (-1, 0), (0, 1), (1, 0), (0, -1), (1, 0), (-1, 0), (0, 1), (1, 0), (-1, 0), (0, -1), (-1, 0), (0, 1), (0, -1), (1, 0), (1, 0), (-1, 0), (-1, 0), (1, 0), (1, 0), (0, 1), (0, 1), (-1, 0), (0, -1), (-1, 0), (1, 0), (1, 0), (-1, 0), (0, -1), (0, 1), (1, 0), (-1, 0), (1, 0), (0, -1), (0, 1), (0, -1), (-1, 0), (0, 1), (-1, 0), (1, 0), (0, -1), (-1, 0), (0, 1), (1, 0), (0, -1), (1, 0), (0, 1), (0, 1), (0, -1), (-1, 0), (1, 0), (-1, 0), (-1, 0), (1, 0), (0, 1), (1, 0), (-1, 0), (-1, 0), (1, 0), (-1, 0), (1, 0), (0, -1), (0, 1), (0, -1), (0, -1), (0, 1), (-1, 0), (0, 1), (0, -1), (1, 0), (1, 0), (-1, 0), (0, 1), (0, -1), (0, 1), (1, 0), (0, -1), (0, 1), (0, -1), (0, -1), (0, 1), (0, 1), (-1, 0), (1, 0), (-1, 0), (0, -1), (1, 0), (-1, 0), (-1, 0), (0, -1), (1, 0), (0, 1), (-1, 0), (1, 0), (1, 0), (0, -1), (-1, 0), (0, 1), (1, 0), (-1, 0), (1, 0), (-1, 0), (0, -1), (1, 0), (0, 1), (0, -1), (-1, 0), (-1, 0), (1, 0), (0, 1), (0, -1), (0, 1), (-1, 0), (1, 0), (1, 0), (0, -1), (0, 1), (-1, 0), (0, -1), (1, 0), (-1, 0), (0, 1), (0, 1), (1, 0), (-1, 0), (0, -1), (0, 1), (-1, 0), (1, 0), (0, -1), (1, 0), (-1, 0), (-1, 0), (1, 0), (0, 1), (1, 0), (0, -1), (-1, 0), (-1, 0), (1, 0), (0, -1), (0, 1), (0, 1), (-1, 0), (0, -1), (0, -1), (0, 1), (0, 1), (0, -1), (0, 1), (1, 0), (1, 0), (-1, 0), (0, -1), (-1, 0), (0, -1), (1, 0), (0, 1), (1, 0), (-1, 0), (0, -1), (-1, 0), (0, 1), (1, 0), (0, -1), (1, 0), (0, 1), (0, 1), (0, -1), (0, -1), (0, 1), (-1, 0), (-1, 0), (1, 0), (0, 1), (0, -1), (1, 0), (-1, 0), (0, -1), (0, 1), (0, -1), (-1, 0), (0, 1), (0, -1), (1, 0), (1, 0), (0, 1), (-1, 0), (0, -1), (1, 0), (0, 1), (0, 1), (-1, 0), (-1, 0), (0, -1), (1, 0), (-1, 0), (1, 0), (1, 0), (0, 1), (0, -1), (-1, 0), (0, 1), (0, -1), (0, -1), (1, 0), (0, 1), (-1, 0), (1, 0), (-1, 0), (1, 0), (0, 1), (-1, 0), (1, 0), (-1, 0), (1, 0), (-1, 0), (-1, 0), (1, 0), (1, 0), (0, -1), (-1, 0), (-1, 0), (0, -1), (1, 0), (0, 1), (0, 1), (-1, 0), (0, -1), (0, -1), (1, 0), (0, 1), (-1, 0), (1, 0), (0, 1), (1, 0), (-1, 0), (-1, 0), (1, 0), (-1, 0), (1, 0), (1, 0), (-1, 0), (0, -1), (0, -1), (0, 1), (0, 1), (0, -1), (1, 0), (-1, 0), (-1, 0), (0, 1), (0, -1), (1, 0), (0, 1), (1, 0), (-1, 0), (-1, 0), (0, -1), (0, -1), (1, 0), (0, 1), (0, -1), (-1, 0), (1, 0), (1, 0), (0, 1), (-1, 0), (0, -1), (1, 0), (-1, 0), (1, 0), (0, 1), (0, -1), (-1, 0), (0, 1), (0, 1), (0, -1), (1, 0), (0, 1), (-1, 0), (-1, 0), (1, 0), (0, -1), (0, 1), (1, 0), (-1, 0), (-1, 0), (0, -1), (1, 0), (1, 0), (0, -1), (0, 1), (0, 1)
--Alec 14:42, 9 January 2010 (UTC)
