Experimental results

To return to the main Polymath5 page, click here.

Perhaps we should have two kinds of subpages to this page: Pages about finding examples, and pages about analyzing them?

Experimental data

• 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
• Sequences taking values in [math]\displaystyle{ \mathbb{T} }[/math]:
  • 4th roots of unity
  • 6th roots of unity
• A sequence of length 407 with discrepancy 2 such that [math]\displaystyle{ x_n=x_{32 n} }[/math] for every n. The HAP-subsequence structure of that sequence.
• More T32-invariant sequences.
• Long multiplicative sequences.
• Long sequences satisfying T2(x) = -T(x) T_2(x)=-x. This should surely say T2(x)=-x, but I don't seem to be able to change the title of the page.

Wish list

• Find long/longest quasi-multiplicative sequences with some fixed group G, function [math]\displaystyle{ G\to \{-1,1\} }[/math] and maximal discrepancy C
  • [math]\displaystyle{ G=C_6 }[/math] and the function that sends 0,1 and 2 to 1 (because this seems to be a good choice)
• Do a "Mark-Bennet-style analysis" of one of the new 1124-sequences. [1] Also done (by Mark Bennet).
• . Take a moderately large k and search for the longest sequence of discrepancy 2 that's constructed as follows. First, pick a completely multiplicative function f to the group [math]\displaystyle{ C_{2k} }[/math]. Then set [math]\displaystyle{ x_n }[/math] to be 1 if f(n) lies between 0 and k-1, and -1 if f(n) lies between k and 2k-1. Alec has already done this for k=1 and partially done it for k=3.
• Search for the longest sequence of discrepancy 2 with the property that [math]\displaystyle{ x_n=x_{32n} }[/math] for every n. The motivation for this is to produce a fundamentally different class of examples (different because their group structure would include an element of order 5). It's not clear that it will work, since 32 is a fairly large number. However, if you've chosen [math]\displaystyle{ x_{32n} }[/math] then that will have some influence on several other choices, such as [math]\displaystyle{ x_{4n},x_{8n} }[/math] and [math]\displaystyle{ x_{16n} }[/math], so maybe it will lead to something interesting. Alec has made a start on this and an initial investigation suggests that the sequence he has found does indeed have some [math]\displaystyle{ C_{10} }[/math]-related structure.
• Here's another experiment that should be pretty easy to program and might yield something interesting. It's to look at the how the discrepancy appears to grow when you define a sequence using a greedy algorithm. I say "a" greedy algorithm because there are various algorithms that could reasonably be described as greedy. Here are a few.

1. For each n let [math]\displaystyle{ x_n }[/math] be chosen so as to minimize the discrepancy so far, given the choices already made for [math]\displaystyle{ x_1,\dots,x_{n-1} }[/math]. (If this does not uniquely determine [math]\displaystyle{ x_n }[/math] then choose it arbitrarily, or randomly, or according to some simple rule like always equalling 1.)

2. Same as 1 but with additional constraints, in the hope that these make the sequence more likely to be good. For instance, one might insist that [math]\displaystyle{ x_{2k}=x_{3k} }[/math] for every k. Here, when choosing [math]\displaystyle{ x_n }[/math] one would probably want to minimize the discrepancy up to [math]\displaystyle{ x_{n+k} }[/math] if [math]\displaystyle{ x_{n+1},\dots,x_{n+k} }[/math] had already been chosen. Another obvious constraint to try is complete multiplicativity.

3. A greedy algorithm of sorts, but this time trying to minimize a different parameter. The first algorithm will do this: when you pick [math]\displaystyle{ x_n }[/math] you look, for each factor d of n, at the partial sum along the multiples of d up to but not including n. This will give you a set A of numbers (the possible partial sums). If max(A) is greater than max(-A) then you set [math]\displaystyle{ x_n=-1 }[/math], if max(-A) is greater than max(A) then you let [math]\displaystyle{ x_n=1 }[/math], and if they are equal then you make the decision according to some rule that seems sensible. But it might be that you would end up with a slower-growing discrepancy if you regarded A as a multiset and made the decision on some other basis. For instance, you could take the sum of [math]\displaystyle{ 2^k }[/math] over all positive elements [math]\displaystyle{ k\in A }[/math] (with multiplicity) and the sum of [math]\displaystyle{ 2^{-k} }[/math] over all negative elements and choose [math]\displaystyle{ x_n }[/math] according to which was bigger. Although that wouldn't minimize the discrepancy at each stage, it might make the sequence better for future development because it wouldn't sacrifice the needs of an overwhelming majority to those of a few rogue elements.

The motivation for these experiments is to see whether they, or some variants, appear to lead to sublogarithmic growth. If they do, then we could start trying to prove rigorously that sublogarithmic growth is possible. I still think that a function that arises in nature and satisfies f(1124)=2 ought to be sublogarithmic.

• What happens if one applies a backtracking algorithm to try to extend the following discrepancy-2 sequence, which satisfies [math]\displaystyle{ x_{2n}=-x_n }[/math] for every n, to a much longer discrepancy-2 sequence: + - - + - + + - - + + - + - + + - + - - + - - + + - - + + - + - - + - - + + + + - - - + + + - - + - + + - + - - + - ?

• ... you are welcome to add more.