The behavior of a certain greedy algorithm for Erdős Discrepancy Problem - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T01:59:51Z http://mathoverflow.net/feeds/question/105383 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105383/the-behavior-of-a-certain-greedy-algorithm-for-erds-discrepancy-problem The behavior of a certain greedy algorithm for Erdős Discrepancy Problem Gil Kalai 2012-08-24T12:31:50Z 2012-09-05T15:18:25Z <p>Let $N$ be a positive integer. We want to find a completely multiplicative functions f(n) with values $\pm 1$ for $n \le N$ such that the discrepancy $$D=\max_{n \le N} |{\sum_{i=1}^nf(i)}|$$ is as small as possible. This is Erdős Discrepancy problem for multiplicative functions.</p> <p>Consider the following greedy algorithm:</p> <p>After you assigned the values $f(2),f(3),\dots f(p_i)$ for the first $i$ primes assign the value $f(p_{i+1})$ so as to minimize the maximum discrepancy $|{\sum_{i=1}^nf(i)}|$ in every partial sum where unassigned entries of $f$ get the value zero.</p> <blockquote> <p>Question: How does this greedy algorithm perform?</p> </blockquote> <p>Experimental or heuristic answers as well as rigorous proofs are welcomed.</p> <p>For more background and related questions see <a href="http://gowers.wordpress.com/2012/08/22/edp22-first-guest-post-from-gil-kalai/" rel="nofollow">this post </a>.</p> <h2>Variation</h2> <p>Consider the same greedy algorithm when you impose the condition that $f(m)=0$ unless $m$ is square free. (If $m$ is not square free $f$ is multiplicative and has values $\pm1$.)</p> <blockquote> <p>Question: How does our greedy algorithm performs on the square-free version?</p> </blockquote> <p>Namely, we would like to understand the behavior of the discrepancy of the function obtained by our greedy algorithm. While for EDP there are known examples with $\log N$ discrepancy, this is not known for the square-free version.</p> <h2>Update:</h2> <p>The very nice answer by rlo suggests that the greedy algorithm gives discrepancy close to $n^{1/3}$ or so, and rlo expect it also for the square free variation. Can an upper bound of $N^{1/2-\epsilon}$ be proved? What about a lower bound of $N^{\epsilon}$. Another interesting question is if you can improve the greedy algorithm to get lower discrepancy. Our greedy ignore 0's in intervals. A greedy algorithm that ignore intervals with 0's was considered in polymath5 and to the best of my memory achieve discrepancy $n^{1/2}$. Maybe a clever interpolation between these two variants will do a better job than both? </p> <h2>Further meditation and a new variant</h2> <p>It seems that in our greedy algorithm the decisions we make for small primes are fairly irrelevant. A way to check it: </p> <blockquote> <p>Run the algorithm for N and test what is the discrepancy for an interval [1,T] where T is, say, $\sqrt N$. I would expect the answer to be roughly $\sqrt T$.</p> </blockquote> <p>So now we can think about the following variation: </p> <p>Let $a>1$ be a real number. We run the greedy algorithm above but our decision for $f(p)$ is based only on intervals $[1,n]$ where $n \le p^a$. (Of course we consider only $n \le N$. </p> <blockquote> <p><strong>Questions: Can this variant lead to lower discrepancy?</strong></p> <p><strong>What is the optimal value of $a$?</strong></p> </blockquote> http://mathoverflow.net/questions/105383/the-behavior-of-a-certain-greedy-algorithm-for-erds-discrepancy-problem/105420#105420 Answer by rlo for The behavior of a certain greedy algorithm for Erdős Discrepancy Problem rlo 2012-08-24T20:41:47Z 2012-08-25T23:13:03Z <p><strong>Update 2:</strong> Original answer below. I've put together graphs showing more than just champions, using every $N\leq 10^4$ and also every $N\equiv 0\pmod{100}$ up to $10^5$. This is for the original version, not the variant, but I'd expect that to be essentially the same. I am starting to be somewhat skeptical of my $1/3$ estimate. I'll collect some data further out, but it'll be less complete since it's more costly to collect.</p> <p>Here's the graphs of $D(N)$ versus $N$. The added curves are $N^{1/3}$ and $\log N$. <img src="http://www.mathcs.emory.edu/~rlemkeo/edp/disc_4.png" alt="alt text"> <img src="http://www.mathcs.emory.edu/~rlemkeo/edp/disc_5.png" alt="alt text"></p> <p>Here's the graph of $\log D/\log N$ versus $N$. The horizontal line is at $1/3$. (Note the different scales.) <img src="http://www.mathcs.emory.edu/~rlemkeo/edp/logd_4.png" alt="alt text"> <img src="http://www.mathcs.emory.edu/~rlemkeo/edp/logd_5.png" alt="alt text"></p> <p><strong>Original answer:</strong> I have some basic numerical observations. I hacked together some code in c++ to work on this, and would be happy to collect more focused data or to share the code. Also, whenever there was a choice of whether to assign the value $+1$ or $-1$ to $f(p)$, I chose $-1$ for consistency of output. This yields a well-defined function $f_N$ for each $N$. Let $D(N)$ denote the discrepancy of $f_N$ up to $N$. </p> <p>(I've also looked at choosing $f(p)=+1$ if it's undetermined, and at $f(p)=\pm 1$ according to whether $p\equiv 1,3\pmod{4}$. In these cases, the data is essentially the same as below.)</p> <ol> <li><p>$D(N)$ is roughly increasing, but is not monotonic. Its champion values for $N\leq10000$ are, in the form $(N,D(N))$, $(1,1)$,$(10,2)$,$(24,3)$,$(70,5)$,$(91,6)$,$(391,7)$,$(553,8)$,$(668,9)$,$(961,10)$,$(1235,11)$,$(1265,13)$,$(2561,14)$,$(2604,17)$,$(6275,18)$,$(6276,19),\dots$. This growth is more than logarithmic, and is probably polynomial -- $\log D/\log N$ hovers pretty close to $1/3$ for each of these points, so that may be the answer for the $\Omega$ result.</p></li> <li><p>It appears that the functions $f_N$ may converge as $N\to\infty$, but I'm not sure of this and need more data. Let $l(N)$ denote the least prime $p$ for which the value of $f_N(p)$ is undetermined. Certainly $l(N)\geq 5$ once $N\geq 4$, and while there is a great deal of fluctuation, it appears that maybe $l(N)\geq 7$ once $N\geq40500$; I will be seeing if this is (numerically) true.</p></li> </ol> <p>I hope to update this answer once I have more data.</p> <p><strong>Update:</strong> For the variation where we only look at the values of $f_N$ on squarefree integers, the behavior appears to be the same.</p> <p>$(N,D(N),\log D/\log N)$:</p> <ul> <li>$(1,1,\text{NaN})$</li> <li>$(30,2,0.2037950471)$</li> <li>$(42,3,0.2939297479)$</li> <li>$(77,4,0.3191428313)$</li> <li>$(190,5,0.3067334722)$</li> <li>$(238,6,0.3274252273)$</li> <li>$(319,8,0.3606890916)$</li> <li>$(939,9,0.3210056698)$</li> <li>$(1358,10,0.3191931033)$</li> <li>$(1461,11,0.3290703914)$</li> <li>$(2185,13,0.3335707591)$</li> <li>$(2769,14,0.3329519195)$</li> <li>$(3354,15,0.3335896252)$</li> <li>$(3689,17,0.3449622741)$</li> </ul> http://mathoverflow.net/questions/105383/the-behavior-of-a-certain-greedy-algorithm-for-erds-discrepancy-problem/105432#105432 Answer by Joseph O'Rourke for The behavior of a certain greedy algorithm for Erdős Discrepancy Problem Joseph O'Rourke 2012-08-25T00:24:09Z 2012-08-25T01:51:01Z <p>Here is a plot of <em>rlo</em>'s data (as listed in his/her item (1)): <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/PlotDN.jpg" alt="Plot D(N)"><br /> <hr /> And here is the $\log D(N) / \log N$ ratio he mentioned in the comment (where the constant red line is $\frac{1}{3}$): <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/PlotLogDLogN.jpg" alt="Plot LogD/LogN"><br /></p>