Experimental results: Difference between revisions

From Polymath Wiki
Jump to navigationJump to search
← Older editNewer edit →
SuneJ (talk | contribs)
48 edits
No edit summary
SuneJ (talk | contribs)
48 edits
No edit summary
Line 1: Line 1:
To return to the main Polymath5 page, click [[The Erdős discrepancy problem|here]].
To return to the main Polymath5 page, click [[The Erdős discrepancy problem|here]].


[[The first 1124-sequence]] with discrepancy 2.


Other [[length 1124 sequences]] with discrepancy 2.
[[The first 1124-sequence]] with discrepancy 2. ''Some more description''


== Varying the upper and lower bounds ==
Other [[length 1124 sequences]] with discrepancy 2. ''Some more description''


If <math>N(a,b)</math> is the maximum length of a <math>\pm 1</math> sequence with the partial sums along its HAPs bounded below by <math>-a</math> and above by <math>b</math>, then:
Some data about the problem with [[different upper and lower bound]]. ''Some more description''


<math>N(a, b) = N(b, a)</math>


<math>N(0, b) = b</math> (everything must be <math>+1</math>)
<math>N(1, 1) = 11</math> (there are <math>4</math> such sequences: choose <math>x_1</math>, and use the constraints <math>x_n +x_{2n} = 0</math> and <math>x_1 + \ldots + x_{2n} = 0</math> to determine the entries up to <math>10</math>; then choose <math>x_{11}</math>)
<math>N(1, 2) = 41</math> (there are <math>4</math> such sequences -- example below)
0 + - - + - + + - + + - - +
- + + - + - - - + - + + - -
+ + - + - + + - - - + - + +
<math>N(1, 3) = 83</math> (there are <math>216</math> such sequences -- example below)
0 - + - + - + + - + + - - +
- + + - - + - - + - + + - +
+ + - - - + + - + + - - + -
+ - - + + - - + - + + + - +
- - - + + - + - + - - + - +
+ - + + - - + - + - - - + +
<math>N(1, 4) = 131</math> (there are <math>87144</math> such sequences -- example below)
0 + - - + - + + - - + -
+ + - + + + + - - - + -
- + - + + - - + + + - -
- + + - + - + - - + + -
+ + - - + - - + - + + +
+ - - + - + - - + + + -
+ - - - - + + - - - + +
- - + + + + - - - - + +
- + - + + + + - - + + -
+ - - - + + - - - + - -
+ + + - + + - - + - - +
<math>N(2, 2) \geq 1124</math>
--[[User:Alec|Alec]] 13:46, 9 January 2010 (UTC)


== Geometric variations ==
== Geometric variations ==

Revision as of 10:47, 9 January 2010

To return to the main Polymath5 page, click here.


The first 1124-sequence with discrepancy 2. Some more description

Other length 1124 sequences with discrepancy 2. Some more description

Some data about the problem with different upper and lower bound. Some more description


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)

Retrieved from "https://michaelnielsen.org/polymath/index.php?title=Experimental_results&oldid=2485"