I have a doubt, Roth's discrepancy theorem [1] says that there is a subset of arithmetic progressions $A \in [n]$ where any function $f:N\rightarrow \left \{ -1,1 \right \} $ implies

$ \left | \sum _{a\in A}f(a) \right |\geq cn^{1/4} $

(Does not specify if the arithmetic progression is homogeneous or not homogeneous)

In 2015 Terence Tao [2] proved for any homogeneous arithmetic progression we have

$Sup_{n,d\in N}\left | \sum^{n} _{j=1}f(jd) \right |=\infty$

It occurred to me to ask if the discrepancy is infinite for non-homogeneous arithmetic progressions or is it an open question

[1]Roth, K. F. Remark concerning integer sequences. Acta Arith. 9 1964 257–260.

[2] Tao, Terence (2016). "The Erdős discrepancy problem". Discrete Analysis: 1–29. arXiv:1509.05363


The discrepancy for arbitrary Arithmetic Progessions over the natural numbers (of which Homogeneous APs are a subset) was indeed shown by Roth to be infinite. But he showed more, with a lower bound of $c\cdot n^{1/4}$ for the progressions restricted to the set $\{1,2,\ldots,n\}$. This bound was later proved to be essentially tight.

Interestingly, Lovasz used Semidefinite programming to derive the result with $c=1/49.$

Tao's result shows that the discrepancy restricted to homogeneous AP's is also infinite. However, as of now, there is no effective lower bound on the discrepancy of homogeneous APs restricted to $\{1,2,\ldots,n\}.$


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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