20
$\begingroup$

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 expects 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?

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$?

$\endgroup$
7
  • $\begingroup$ Right sorry I meant completely multiplicative. $\endgroup$
    – Gil Kalai
    Aug 24, 2012 at 13:20
  • 2
    $\begingroup$ Are we requiring $f(n)$ to be $\pm 1$ only? $\endgroup$
    – rlo
    Aug 24, 2012 at 15:03
  • $\begingroup$ yes. (We can also think of a variant with complex values of norm 1) $\endgroup$
    – Gil Kalai
    Aug 24, 2012 at 15:58
  • $\begingroup$ It is still unclear. Suppose I start by assigning fK2), and propogate the result to all powers of 2. I get two infinite vectors of partial sums. How do I determine which vector I prefer so that I decide which choice I like? Do I consider all values, or just finitely many? Gerhard "Even Large Numbers Concern Me" Paseman, 2012.08.24 $\endgroup$ Aug 24, 2012 at 16:30
  • 1
    $\begingroup$ @Gerhard Paseman: You fix some $N$. Then run the algo to get some function (up to $N$). Then compute its discrepancy. How will these discrepancies behave (as a function of $N$). $\endgroup$
    – user9072
    Aug 24, 2012 at 16:59

2 Answers 2

12
$\begingroup$

Update 2: 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.

Here's the graphs of $D(N)$ versus $N$. The added curves are $N^{1/3}$ and $\log N$. enter image description here enter image description here

Here's the graph of $\log D/\log N$ versus $N$. The horizontal line is at $1/3$. (Note the different scales.) enter image description here enter image description here

Original answer: 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$.

(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.)

  1. $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.

  2. 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.

I hope to update this answer once I have more data.

Update: For the variation where we only look at the values of $f_N$ on squarefree integers, the behavior appears to be the same.

$(N,D(N),\log D/\log N)$:

  • $(1,1,\text{NaN})$
  • $(30,2,0.2037950471)$
  • $(42,3,0.2939297479)$
  • $(77,4,0.3191428313)$
  • $(190,5,0.3067334722)$
  • $(238,6,0.3274252273)$
  • $(319,8,0.3606890916)$
  • $(939,9,0.3210056698)$
  • $(1358,10,0.3191931033)$
  • $(1461,11,0.3290703914)$
  • $(2185,13,0.3335707591)$
  • $(2769,14,0.3329519195)$
  • $(3354,15,0.3335896252)$
  • $(3689,17,0.3449622741)$
$\endgroup$
3
  • $\begingroup$ After when $f_N(p)$ the function is periodic. Thus $f_N(p)$ does not depend on $N$ for $N>2\cdot3\cdots p$, and so $f(N)$ converges. It may be hard to compute the limit thought. $\endgroup$
    – Omer
    Sep 23, 2012 at 17:30
  • $\begingroup$ The links seem to have gone away. $\endgroup$ Mar 7, 2014 at 5:19
  • 1
    $\begingroup$ Fixed! Sorry about that. Apparently all the files I'd hosted at Emory before moving have gone away. $\endgroup$
    – rlo
    Mar 7, 2014 at 17:08
8
$\begingroup$

Here is a plot of rlo's data (as listed in his/her item (1)):
          Plot D(N)


And here is the $\log D(N) / \log N$ ratio he mentioned in the comment (where the constant red line is $\frac{1}{3}$):
          Plot LogD/LogN

$\endgroup$
1
  • 1
    $\begingroup$ His. And the ratio of $\log D/\log N$ I alluded to, not in graph form: 0.3010299957, 0.345687124, 0.3788254007, 0.3972102138, 0.3260186782, 0.3302216042, 0.3378116896, 0.3352640758, 0.3368385727, 0.3590944053, 0.336264762, 0.3602395359, 0.3305424391, 0.3367194215. Close enough to 1/3 that I suspect something is happening. $\endgroup$
    – rlo
    Aug 25, 2012 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.