# Difference between revisions of "Experimental results"

(→Experimental data) |
Yangofzeal (Talk | contribs) (→Source code) |
||

Line 22: | Line 22: | ||

* [[Convert raw input string into CSV table]] | * [[Convert raw input string into CSV table]] | ||

* [[Create tables in an HTML file from an input sequence]] | * [[Create tables in an HTML file from an input sequence]] | ||

+ | * [[Verify the bounded discrepancy of sequence]] | ||

==Wish list== | ==Wish list== |

## Revision as of 11:43, 11 January 2010

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. Let N(a,b) be the largest N such that there is a sequence [math]x_1,\dots,x_N[/math] all of whose HAP-errors are between -a and b, inclusive.
- Sequences taking values in [math]\mathbb{T}[/math]:
- A sequence of length 407 with discrepancy 2 such that [math]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) = -x.
- Long sequences satisfying T2(x) = T5(x) = -x
- Long sequences satisfying T2(x) = -T3(x).
- Long sequences satisfying constraints of the form T_m(x) = (+/-)T_n(x)

## Source code

- Convert raw input string into CSV table
- Create tables in an HTML file from an input sequence
- Verify the bounded discrepancy of sequence

## Wish list

- Find long/longest quasi-multiplicative sequences with some fixed group G, function [math]G\to \{-1,1\}[/math] and maximal discrepancy C
- [math]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]C_{2k}[/math]. Then set [math]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]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]x_{32n}[/math] then that will have some influence on several other choices, such as [math]x_{4n},x_{8n}[/math] and [math]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]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]x_n[/math] be chosen so as to minimize the discrepancy so far, given the choices already made for [math]x_1,\dots,x_{n-1}[/math]. (If this does not uniquely determine [math]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]x_{2k}=x_{3k}[/math] for every k. Here, when choosing [math]x_n[/math] one would probably want to minimize the discrepancy up to [math]x_{n+k}[/math] if [math]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]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]x_n=-1[/math], if max(-A) is greater than max(A) then you let [math]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]2^k[/math] over all positive elements [math]k\in A[/math] (with multiplicity) and the sum of [math]2^{-k}[/math] over all negative elements and choose [math]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]x_{2n}=-x_n[/math] for every n, to a much longer discrepancy-2 sequence: + - - + - + + - - + + - + - + + - + - - + - - + + - - + + - + - - + - - + + + + - - - + + + - - + - + + - + - - + - ? This question has been answered in the comments following the asking of the question on the blog.

- Investigate what happens if our HAPs are restricted to allow differences divisible only by 2 or 3 [and then other sets of primes including 2] - {2,3,5,7} would be interesting - is there an infinite sequence of discrepancy 2 in these simple cases - is it easy to find an infinite sequence with finite discrepancy in these cases? [for sets of odd primes, take a sequence which is 1 on odd numbers, -1 on even numbers. Including 2 is the non-trivial case]. It is possible that completely multiplicative sequences could be found for some of these cases.

- ... you are welcome to add more.