Discrepancy of (centered) arithmetic progressions in \({\mathbb{Z}_p}\) (Q2509760)

The investigations of the combinatorial discrepancy of arithmetic progressions are very important for the probabilistic methods in the combinatorics. In the present paper the problem for an estimation of the \(c\)-color discrepancy, \(c \geq 2,\) of arithmetic progressions and centered arithmetic progressions is considered. It is shown that for both hypergraphs, the lower bound is tight up to a logarithmic factor in \(p\) than the upper bound. More precise, the lower bound is \(\Omega \left(\sqrt{p \over c}\right)\) and the upper bound is \({\mathcal O}\left(\sqrt{{p \over c} \ln p}\right).\) In the Introduction of the paper the notion of the multicolor discrepancy, or the \(c\)-color discrepancy is presented. Some previously results related with the multicolor discrepancy are reminded. The important structural difference between an arithmetic progression and a centered arithmetic progression is discussed. In Section 2 the notion of \(\mathbb{Z}_p\)-invariant hypergraph is presented. In Theorem 1 a low estimation of the coloring function on \(\mathbb{Z}_p\) is given. This is the basis for the investigation of the coloring function. In Section 3 the discrepancy of arithmetic progressions in \(\mathbb{Z}_p\) is investigated. In Theorem 3 the discrepancy of the hypergraph of the arithmetic progressions in \(\mathbb{Z}_p\) is estimated. It is shown that there exists a constant \(\alpha > 0\) such that the \(c\)-color discrepancy of the hypergraph of the arithmetic progressions in \(\mathbb{Z}_p\) satisfies the inequality \(\displaystyle {1 \over 3} \sqrt{p \over c} \leq \mathrm{disc}({\mathcal H}_{\mathbb{Z}_p}, c) \leq \alpha \sqrt{{p \over c}\ln p} + 1.\) In Section 4 a lower and an upper bound for the \(c\)-color discrepancy \((c \geq 3)\) of the hypergraph of centered arithmetic progressions in \(\mathbb{Z}_p\) is given. In Theorem 4 it is shown that the \(c\)-color discrepancy \((c \geq 3)\) of the hypergraph of centered arithmetic progressions in \(\mathbb{Z}_p\) satisfies the inequalities \(\displaystyle {1 \over 31} \sqrt{p \over c} \leq \mathrm{disc}({\mathcal H}_{\mathbb{Z}_p}, c) \leq \alpha \sqrt{{p \over c}\ln p} + 1\) with some positive constant \(\alpha.\) To the end of this section Theorem 4 is proved. In Section 5 some open problems are discussed.