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.
Consider the following greedy algorithm:
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.
Question: How does this greedy algorithm perform?
Experimental or heuristic answers as well as rigorous proofs are welcomed.
For more background and related questions see this post .
Variation
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$.)
Question: How does our greedy algorithm performs on the square-free version?
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.
Update:
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}$. 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?
Further meditation and a new variant
It seems that in our greedy algorithm the decisions we make for small primes are fairly irrelevant. A way to check it:
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$.
So now we can think about the following variation:
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$.
Questions: Can this variant lead to lower discrepancy?
What is the optimal value of $a$?
