Archive for September 19th, 2012

EDP27 — the modular version of Roth’s AP-discrepancy theorem

September 19, 2012

Recall from earlier posts Gil’s modular conjecture for HAPs. It states that if n is large enough and f is a function from \{1,2,\dots,n\} to \mathbb{Z}_p that never takes the value 0, then for every a there exists a HAP P such that \sum_{x\in P}f(x)\equiv a mod p. It is easy to see that this implies EDP, so it may well be very hard, or even false. However, one can hold out a little hope that, as with some strengthenings of statements, it is in fact easier, because it is in some way more symmetrical and fundamental. Given that, it makes good sense, as Gil has suggested, to try to prove modular versions of known discrepancy theorems, in the hope of developing general techniques that can then be tried out on the modular EDP conjecture.

A very obvious candidate for a discrepancy theorem that we could try to modularize is Roth’s theorem, which asserts that for any \pm 1-valued function f on \{1,2,\dots,n\} there exists an arithmetic progression P such that |\sum_{x\in P}f(x)|\geq cn^{1/4}. That gives rise to the following problem.

Problem. Let p be a prime. What is the smallest n such that for every function f:\{1,2,\dots,n\}\to\mathbb{Z}_p that never takes the value 0, every a\in\mathbb{Z}_p can be expressed as \sum_{x\in P}f(x) for some arithmetic progression P?

In this post I shall collect together a few simple observations about this question.