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.

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? ## Furthermeditationandanewvariant 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$? 5 added 634 characters in body 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}$. 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? 4 added 510 characters in body 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.

3 added 33 characters in body
2 typo
1