Proof. Let $\operatorname {AP}_n(a, d, i, j) := \{a+kd: i\leq k \leq j\}$ where $a, d\in \mathbb {Z}_n$ and $i, j\in \mathbb {Z}$. By definition,

\[ \mathcal{A}_n = \bigg\{\operatorname{AP}_n(a, d, 0, l-1): a, d\in \mathbb{Z}_n,\ 0\leq l \leq \frac{n}{\gcd(n, d)}\bigg\}. \]

Consider the following decomposition of sets in $\mathcal {A}_n$. Let

\[ C_1 = \bigg\{\operatorname{AP}_n(a, d, i, j): 1\leq d < n,\ 0\leq a < \gcd(n, d),\ 0\leq i\leq j < \frac{n}{\gcd(n, d)}\bigg\}. \]

Now we show that any set $A\in \mathcal {A}_n$ can be written as the disjoint union of at most two sets in $C_1$. For any set $A = \operatorname {AP}_n(a, d, 0, l-1)$ with $a, d\in \mathbb {Z}_n$ and $0\leq l \leq {n}/{\gcd (n, d)}$, we may assume that $l > 0$, or otherwise it is an empty set. If $d = 0$, then the set is the singleton $\{a\}$, which is also $\operatorname {AP}_n(0, 1, a, a)\in C_1$ by choosing $i, j$ to be the integer representative of $a$ in the range $[0, n)$. Now we may assume $1 \leq d < n$. Note that $\{kd: 0\leq k < {n}/{\gcd (n, d)}\}$ splits $\mathbb {Z}_n$ into ${n}/{\gcd (n, d)}$ equal-sized intervals, so there is some $0\leq k < {n}/{\gcd (n, d)}$ such that $0\leq a - kd < \gcd (n, d)$. Define $a' = a - kd$, and we have

\[ \operatorname{AP}_n(a, d, 0, l - 1) = \operatorname{AP}_n(a', d, k, k + l - 1). \]

Moreover, we have $k < {n}/{\gcd (n, d)}$ and $l -1 < {n}/{\gcd (n, d)}$, so $0\leq k+l-1 < 2( {n}/{\gcd (n, d)})$. If $k+l-1 < {n}/{\gcd (n, d)}$, then $\operatorname {AP}_n(a', d, k, k+l-1)\in C_1$. If $k + l-1\geq {n}/{\gcd (n, d)}$, then we may write

\[ \operatorname{AP}_n(a', d, k, k+l-1) = \operatorname{AP}_n\bigg(a', d, k, \frac{n}{\gcd(n, d)}-1\bigg) \cup \operatorname{AP}_n\bigg(a', d, 0, k+l -1- \frac{n}{\gcd(n, d)}\bigg). \]

Hence, we know that for any partial coloring $\chi : \mathbb {Z}_n \to \{-1, 0, 1\}$, we always have

(2.2)\begin{equation} \max_{A\in \mathcal{A}_n}|\chi(A\cap X)| \leq 2 \max_{A\in C_1}|\chi(A\cap X)|. \end{equation}

Now we study the sets in $C_X := \{A\cap X: A\in C_1\}$. By definition, we have

(2.3)\begin{equation} \max_{A\in C_1}|\chi(A\cap X)| = \max_{B\in C_X}|\chi(B)|. \end{equation}

For each $1\leq d < n$ and $0\leq a < \gcd (n, d)$, we define $A_{d, a} = \{a+kd: 0\leq k < {n}/{\gcd (d, n)}\}$, and define $X_{d, a} = A_{d, a}\cap X$. As each element $x$ in $X_{d, a}$ is associated with an integer $0\leq k < {n}/{\gcd (d, n)}$ via the relation $x = a+kd$, we may order elements in $X_{d, a}$ in ascending order of $k$. We write $X_{d, a} = \{x_{d, a}^{(1)}, \ldots, x_{d, a}^{(l_{d, a})}\}$, where $l_{d, a} = |X_{d, a}|$. For integers $i$ and $j$, we define $X_{d, a}(i, j) = \{x_{d, a}^{(t)}: i \leq t \leq j\}$.

For each $d\in \mathbb {Z}_n$, because each element of $\mathbb {Z}_n$ is in exactly one $A_{d, a}$ for $0\leq a < \gcd (d, n)$, we have

(2.4)\begin{equation} \sum_{a = 0}^{\gcd(d, n) - 1}l_{d, a} = \sum_{a = 0}^{\gcd(d, n) - 1}|X\cap A_{d, a}| = |X| = m. \end{equation}

For $A = \operatorname {AP}_n(a, d, i, j)$, if we take $i'$ to be the smallest index such that $x_{d, a}^{(i')} = a + k_1d$ with $k_1 \geq i$ (or $l_{d, a}+1$ if no such index with $0\leq k_1 < {n}/{\gcd (d, n)}$ exists), and $j'$ to be the largest index such that $x_{d, a}^{(j')} = a+k_2d$ with $k_2 \leq j$ (or $0$ if no such index with $0\leq k_2 < {n}/{\gcd (d, n)}$ exists), then we have $A\cap X = X_{d, a}(i', j')$. Hence, each nonempty set in $C_X$ is of the form $X_{d, a}(i, j)$ with $1\leq i \leq j \leq l_{d, a}$. Therefore, we may write

\[ C_X = \{X_{d, a}(i, j): 1\leq d < n,\ 0\leq a < \gcd(n, d),\ 1\leq i\leq j \leq l_{d, a}\} \cup \{\emptyset\}. \]

Now we further decompose sets in $C_X$ into canonical sets. Formally,

(2.5)\begin{equation} C_2 := \bigg\{X_{d, a}(1+(t-1)2^i, t2^i): 1\leq d < n,\ 0\leq a < \gcd(n, d),\ 0\leq i,\ 1\leq t \leq \bigg\lfloor\frac{l_{d, a}}{2^i}\bigg\rfloor\bigg\}. \end{equation}

Note that each set $S\in C_X$ can be written as $U\setminus V$ with $V\subseteq U$ where both $U$ and $V$ can be written as the disjoint union of sets in $C_2$ of different sizes. This is trivially true for the empty set. For $S = X_{d, a}(i, j)$, we may take $U = X_{d, a}(1, j)$ and $V = X_{d, a}(1, i-1)$. If we write $j$ in binary form $2^{b_1} + 2^{b_2} + \cdots + 2^{b_s}$ for $b_1 > b_2 > \cdots > b_s$, then $U$ is the disjoint union of sets of the form $X_{d, a}(1+\sum _{k = 1}^{h-1}2^{b_k}, \sum _{k = 1}^{h}2^{b_k})$ for $h = 1, \ldots, s$. We can decompose $V$ similarly.

Note that sets in $C_2$ are all of size $2^i$ for $2^i \leq m$. If $\chi : X\to \{-1, 0, 1\}$ is such that for all $0\leq i\leq \log _2 m$ we have $\chi (S) \leq \Delta _i$ for any set $S\in C_2$ of size $2^i$, then by using the decomposition property above we have

(2.6)\begin{equation} \max_{B\in C_X}|\chi(B)| \leq 2\sum_{0\leq i \leq \log_2 m} \Delta_i. \end{equation}

For each $i$, we upper bound the number of sets in $C_2$ of size $2^i$ as following. For each $1\leq d < n$ and $0\leq a < \gcd (d, n)$, the number of choices of $t$ in (2.5) is $\lfloor {l_{d, a}}/{2^i}\rfloor$. By (2.4) the number of such sets is at most

(2.7)\begin{equation} \sum_{d=1}^{n-1}\sum_{a = 0}^{\gcd(d, n) - 1} \bigg\lfloor\frac{l_{d, a}}{2^i}\bigg\rfloor \leq \sum_{d=1}^{n-1}\sum_{a = 0}^{\gcd(d, n) - 1} \frac{l_{d, a}}{2^i} = \frac{(n-1)m}{2^i}. \end{equation}

Now we define $b(0) = 0$ and for $0 < s \leq n$,

(2.8)\begin{equation} b(s) = 5\sqrt{s} \bigg(\log \frac{en}{s}\bigg)^{1/2}. \end{equation}

From the definition, we know that $b(s) \geq 2\sqrt {s}$ for all $s\in \mathbb {N}$. We want to show that there exists a partial coloring $\chi$ that colors at least $m/10$ elements in $X$, and for any $S\in C_2$,

(2.9)\begin{equation} |\chi(S)| \leq b(|S|). \end{equation}

In order to apply Lemma 2.1 to $X$ and $C = C_2$, it remains to check that

(2.10)\begin{equation} \sum_{S\in C_2} \exp\bigg(-\frac{b(|S|)^2}{4|S|}\bigg) \leq m/50. \end{equation}

From the definition of $b(\cdot )$ in (2.8), we know that

(2.11)\begin{equation} \sum_{S\in C_2} \exp\bigg(-\frac{b(|S|)^2}{4|S|}\bigg) = \sum_{S\in C_2}e^{-{25}/{4}}\cdot \bigg(\frac{|S|}{n}\bigg)^{{25}/{4}} \leq e^{-6}\cdot\sum_{S\in C_2}\bigg(\frac{|S|}{n}\bigg)^2. \end{equation}

Using the bound in (2.7), we have

\[ \sum_{S\in C_2} \bigg(\frac{|S|}{n}\bigg)^{2} \leq \sum_{0\leq i \leq \log_2 m} \frac{(n-1)m}{2^i} \bigg(\frac{2^i}{n}\bigg)^2 \leq 2m. \]

Put this into (2.11). We obtain

\[ \sum_{S\in C_2} \exp\bigg(-\frac{b(|S|)^2}{4|S|}\bigg) \leq e^{-6}\cdot 2m \leq m/50. \]

This shows that (2.10) holds. By Lemma 2.1, we conclude that there exists a partial coloring $\chi : X\to \{-1, 0, 1\}$ that assigns $\pm 1$ to at least $m/10$ elements, and (2.9) holds for any $S\in C_2$. Thus, in (2.6) we may take $\Delta _i = b(2^i)$ for $0\leq i \leq \log _2 m$.

It remains to show that $\chi$ satisfies the desired property. By (2.2), (2.3), and (2.6),

\[ \max_{A\in \mathcal{A}_n}|\chi(A\cap X)| \leq 4\sum_{0\leq i\leq \log_2 m}b(2^i) = 20 \sum_{i = 0}^{\lfloor{\log_2 m}\rfloor} 2^{i/2}\bigg(\log \frac{en}{2^i}\bigg)^{1/2} \leq 200\cdot \sqrt{m}\bigg(\log \frac{en}{m}\bigg)^{1/2}. \]

To obtain the last inequality, observe that the sum is roughly a geometric series with ratio $2^{1/2}$ (although there is an extra logarithmic factor that slightly complicates this) and can be bounded by a constant factor times the largest term. A careful analysis gives the claimed bound.

Hence, the partial coloring $\chi$ satisfies the desired inequality.

Proof. The main idea is to iteratively apply Lemma 2.2 to the set of uncolored elements of $X$ until all elements of $X$ are colored.

Start with $X_0 = X$. For each $i\geq 0$, we apply Lemma 2.2 to $X_i$ to get a partial coloring $\chi _i: X_i \to \{-1, 0, 1\}$, and we let $X_{i+1} = \chi _i^{-1}(0) \subseteq X_i$ to be the set of uncolored elements in $i$th iteration. We continue this process until the $k$th iteration where all elements are colored (i.e. $X_{k+1} = \emptyset$). Let $\chi$ be the final coloring given by $\chi (x_i) = \chi _i(x_i)$ if $x_i\in X_i\setminus X_{i+1}$ for $0\leq i\leq k$. We know that $|X_i| \leq 0.9|X_{i-1}|$ for all $1\leq i\leq k$, so $|X_i| \leq (0.9)^i|X_0| = (0.9)^im$. Moreover, we know that for any $A\in \mathcal {A}_n$, noting that $x^{1/2}\cdot (\log {en}/{x})^{1/2}$ is monotonically increasing for real number $x \in (0, n]$,

\begin{align*} |\chi(A\cap X)| &= \bigg|\sum_{i=0}^k \chi_i(X_i\cap A)\bigg| \leq \sum_{i=0}^k |\chi_i(X_i\cap A)| < \sum_{i=0}^k 200\cdot |X_i|^{1/2}\bigg(\log\frac{n}{e|X_i|}\bigg)^{1/2} \\ &\leq 200m^{1/2}\cdot \sum_{i=0}^k (0.9)^{i/2} \bigg(\log\frac{en}{(0.9)^im}\bigg)^{ 1/2} < cm^{1/2}\bigg(\log\frac{en}{m}\bigg)^{1/2} \end{align*}

for some appropriate choice of the absolute constant $c$.

Proof. Let $m = n/r$. For the subgroup $(m) \subseteq \mathbb {Z}_n$, we have a quotient map $\tau : \mathbb {Z}_n \to \mathbb {Z}_n/(m) = \mathbb {Z}_r$ given by $\tau (x)= \overline {x} = x+(m)$. Suppose we are given an arbitrary $\chi : \mathbb {Z}_r \to \{1, -1\}$. Now we define $\chi ' = \chi \circ \tau : \mathbb {Z}_n\to \{1, -1\}$. It suffices to show

(3.1)\begin{equation} \max_{A'\in \mathcal{A}_{n}} |\chi'(A')| \leq \max_{A\in \mathcal{A}_r}|\chi(A)| + m\cdot \max_{A_0\in \mathcal{A}_r^0}|\chi(A_0)|. \end{equation}

Let $A' = \{a + kd: 0\leq k < L\}$ for some $a, d\in \mathbb {Z}_{n}$ be an arithmetic progression in $\mathbb {Z}_{n}$ of length $L$. We may assume that $L \leq n/{\gcd (d, n)}$ so that there is no repeated element in $A'$.

Let $L_0 = r/\gcd (r, \overline {d})$ where $\overline {d} = \tau (d)$. For any integer $t > 0$, we know that $\{\overline {a} + k\overline {d}: t \leq k < t+L_0\}$ is a set of size $L_0$ in $\mathcal {A}^0_r$, as it covers each element in the congruence class exactly once. For any $0\leq l < L_0$, as the set $\{\overline {a} + k\overline {d}: t \leq k < t+l\}$ has no repeated element, it is a set of size $l$ in $\mathcal {A}_r$.

Now we may write $L = qL_0 + r$ for some integers $q$ and $0\leq r < L_0$. We know that

\[ q\leq \frac{L}{L_0} \leq \frac{n/\gcd(d, n)}{r/\gcd(r, \overline{d})} = m\cdot \frac{\gcd(r, d)}{\gcd(n, d)} \leq m. \]

Applying the triangle inequality, we obtain

\begin{align*} |\chi'(A')| &= \bigg|\sum_{k = 0}^{L-1}\chi'(a+kd)\bigg| = \bigg|\sum_{k = 0}^{L-1}\chi(\overline{a}+k\overline{d})\bigg| = \bigg|\sum_{t = 0}^{q-1}\sum_{k = tL_0}^{(t+1)L_0-1}\chi(\overline{a}+k\overline{d}) + \sum_{k = qL_0}^{qL_0 + r-1}\chi(\overline{a}+k\overline{d})\bigg| \\ &\leq \sum_{t = 0}^{q-1}\bigg|\sum_{k = tL_0}^{(t+1)L_0-1}\chi(\overline{a}+k\overline{d})\bigg| + \bigg|\sum_{k = qL_0}^{qL_0 + r-1}\chi(\overline{a}+k\overline{d})\bigg| \\ &\leq q \cdot \max_{A_0\in \mathcal{A}_r^0}|\chi(A_0)| + \max_{A\in \mathcal{A}_r}|\chi(A)| \leq m\cdot \max_{A_0\in \mathcal{A}_r^0}|\chi(A_0)| + \max_{A\in \mathcal{A}_r}|\chi(A)|. \end{align*}

As the bound is uniform for all $A'\in \mathcal {A}_{n}$, we conclude that (3.1) holds.

Proof Proof of Theorem 3.1 assuming Lemma 3.3

For any positive factor $r$ of $n$, by Lemma 3.3, there is a coloring $\chi$ of $\mathbb {Z}_r$ such that

\[ \max_{A_0\in \mathcal{A}_r^0}|\chi(A_0)| \leq 1 \quad \mathrm{and} \quad \max_{A\in \mathcal{A}_r}|\chi(A)| \leq c\sqrt{r}\cdot 2^{\omega(r)}, \]

where $c$ is an absolute constant. Then applying Lemma 3.2, we conclude that

\[ \operatorname{disc}(\mathcal{A}_n) \leq \frac{n}{r} + c\sqrt{r}\cdot 2^{\omega(r)}. \]

As this holds for all positive factors $r$ of $n$, the desired result follows.

Proof. Let $S = \{0, \ldots, m/2-1\}$. By Corollary 2.3, there is $\chi _0:X\to \{1, -1\}$ such that

\[ |\chi_0(A\cap S)| \leq c_0\sqrt{\frac{m}{2}}\bigg(\log \frac{2en}{m}\bigg)^{ 1/2}, \]

holds for any $A\in \mathcal {A}_n$, where $c_0$ is an absolute constant. We know that $X$ is the disjoint union of $S$ and $S+{m}/{2}$, i.e. each element $x\in X$ is of the form $x = s + v({m}/{2})$ for some $s\in S$ and $v\in \{0, 1\}$. We define $\chi : X \to \{1, -1\}$ given by $\chi (s+v ({m}/{2})) = (-1)^v\cdot \chi _0(s)$ for any $s\in S$ and $v\in \{0, 1\}$.

For any $A\in \mathcal {A}_n$, noting that $A - {m}/{2}$ is also an arithmetic progression,

\begin{align*} |\chi(A\cap X)| &= |\chi(A\cap S) + \chi(A\cap (S+m/2))| = |\chi_0(A\cap S) + (-1)\cdot \chi_0((A-m/2)\cap S)|\\ &\leq |\chi_0(A\cap S)| \,{+}\, |\chi_0((A-m/2)\cap S)| \,{\leq}\, 2\cdot c_0 \sqrt{\frac{m}{2}}\bigg(\log \frac{2en}{m}\bigg)^{1/2} \,{\leq}\, c\sqrt{m}\bigg(\log \frac{en}{m}\bigg)^{1/2}, \end{align*}

where $c$ is an absolute constant. Next we verify that for any $r = p^{\gamma }$ with $\gamma \leq \beta$ and any $w\in \mathbb {Z}_n$, $\chi (C(r, w) \cap X) = 0$. Note that $m/2$ is a multiple of $r$, so $C(r, w) - m/2 = C(r, w)$. Hence, we have

\begin{align*} \chi(C(r, w)\cap X) &= \chi_0(C(r, w)\cap S) + (-1)\cdot \chi_0((C(r, w)-m/2)\cap S) \\ &=\chi_0(C(r, w)\cap S) - \chi_0(C(r, w)\cap S) = 0. \end{align*}

We have thus shown the existence of such a coloring $\chi$ with the desired properties.

Proof of Lemma 3.4 Note that for any $C(r, w)\in \mathcal {A}_n^0$, we have $C(r, w) = C(\gcd (r, n), w)$. Hence, it suffices to check $|\chi (C(r, w))| \leq 1$ where $r$ divides $n = p^\alpha$, i.e. $r = p^\gamma$ for some nonnegative $\gamma \leq \alpha$.

Let $c_0$ be the constant in Lemma 3.5.

If $p = 2$, we can take $m = n = 2\cdot 2^{\alpha -1}$ in Lemma 3.5. Thus, there exists $\chi : \mathbb {Z}_n\to \{1, -1\}$ such that

\[ \max_{A\in \mathcal{A}_n} |\chi(A)| \leq c_0\sqrt{n}, \]

and that for any $w\in \mathbb {Z}_n$ and any $r = 2^{\gamma }$ with $\gamma \leq \alpha -1$, $\chi (C(r, w)) = 0$. This means that, for any $r = 2^\gamma$, if $\gamma \leq \alpha -1$, then $\chi (C(r, w)) = 0$; if $\gamma = \alpha$, then $C(r, w)$ contains a single element $w$, so $|\chi (C(r, w))| = 1$ in this case. We conclude that

\[ \max_{A_0\in \mathcal{A}_n^0}|\chi(A_0)| \leq 1. \]

If $p > 2$ is an odd prime, then we partition $\mathbb {Z}_n$ into a few intervals: $X_0 = \{0\}, X_i = \{x: p^{i-1} \leq x < p^i\}$ for $1\leq i\leq \alpha$. Note that for each $i\geq 1$, $X_i$ is an interval of length $(p-1)\cdot p^{i-1}$. We would like to apply Lemma 3.5 to each $X_i$ for $i\geq 1$. It is applicable because the property is maintained by translation. Therefore, for each $1\leq i\leq \alpha$ there is a coloring $\chi _i: X_i\to \{1, -1\}$ such that

\[ \max_{A\in \mathcal{A}_n} |\chi_i(A\cap X_i)| \leq c_0\sqrt{(p-1)\cdot p^{i-1}} \bigg(1 + \log\frac{p^\alpha}{(p-1)\cdot p^{i-1}}\bigg)^{{1}/{2}}, \]

and for each $w\in \mathbb {Z}_n$ and $r = p^\gamma$ with $\gamma \leq i-1$, we have $\chi _i(C(r, w)\cap X_i) = 0$.

For $X_0$ we may take any arbitrary $\chi _0: X_0 \to \{1, -1\}$. Note that $X_0 = \{0\}$ contains only one element, so $|\chi _0(A\cap X_0)| \leq 1$ for all $A\subseteq \mathbb {Z}_n$.

As $\mathbb {Z}_n = \coprod _{i = 0}^{\alpha }X_i$, we define $\chi : \mathbb {Z}_n\to \{1, -1\}$ such that $\chi (x_i) = \chi _i(x_i)$ for all $0\leq i\leq \alpha$ and $x_i\in X_i$. Consequently, we know that for each $A \in \mathcal {A}_n$,

\[ |\chi(A)| \le \sum_{i = 0}^\alpha |\chi_i(A\cap X_i)| \leq 1 + \sum_{i = 1}^\alpha c_0\sqrt{(p-1)\cdot p^{i-1}} \bigg(1 + \log\frac{p^\alpha}{(p-1)\cdot p^{i-1}}\bigg)^{{1}/{2}} \leq c\sqrt{n} \]

for some appropriate constant $c$. Moreover, for each $C(r, w) \in \mathcal {A}_n^0$, we may assume that $r = p^\gamma$ for some $0\leq \gamma \leq \alpha$ and it gives that

\[ \chi(C(r, w)) = \chi\bigg(C(r, w) \cap \bigg(\bigcup_{i=0}^{\gamma} X_i\bigg)\bigg) + \sum_{i = \gamma+1}^{\alpha}\chi_i(C(r, w)\cap X_i). \]

Now, for each $i \geq \gamma +1$, i.e. $\gamma \leq i-1$, we have $\chi _i(C(r, w)\cap X_i) = 0$. In addition, note that $\bigcup _{i=0}^{\gamma } X_i$ is $\{x: 0\leq x < p^\gamma \}$, so there is exactly one element of $C(r, w)$ in it. Hence,

\[ |\chi(C(r, w))| = \bigg|\chi\bigg(C(r, w) \cap \bigg(\bigcup_{i=0}^{\gamma} X_i\bigg)\bigg)\bigg| = 1. \]

Thus, we may conclude that

\[ \max_{A_0\in \mathcal{A}_n^0}|\chi(A_0)|\leq 1. \]

Hence, for both $p = 2$ and $p$ is odd, we can always find such a coloring $\chi$.

Notation 2 Suppose that number $n$ has prime factorization $n = p_1^{\alpha _1}\cdots p_k^{\alpha _k}$. By Chinese remainder theorem, we have an isomorphism

\[ \psi_n: \mathbb{Z}_{p_1^{\alpha_1}} \times \cdots \times \mathbb{Z}_{p_k^{\alpha_k}} \to \mathbb{Z}_n. \]

Proof. Let $L = |I|$. Let $S_i = T_i/2$ if $i\in I$, and $S_i = T_i$ otherwise. For each $i\in I$, from the condition that $T_i/p_i^{\beta _i}$ is even, we know that $S_i$ is a multiple of $p_i^{\beta _i}$. We define

\[ X_0 = \{\psi_n(t_1, \dots, t_k): 0\leq t_i < S_i\ \mathrm{for\ all}\ \ 1\leq i\leq k\}. \]

We know that $X_0\subseteq \mathbb {Z}_n$ is a set of size $m/2^L$. Next we apply Corollary 2.3 to get the constant $c_0>0$ and a partial coloring of $\chi _0: X_0 \to \{-1, 1\}$ such that

\[ \max_{A\in \mathcal{A}_n} |\chi_0(X_0\cap A)| \leq c_0\sqrt{\frac{m}{2^{L}}} \bigg(1+\log\frac{2^{L}n}{m}\bigg)^{1/2} \leq c\sqrt{\frac{m}{2^{L}}} \bigg(L+1+\log\frac{n}{m}\bigg)^{1/2}, \]

where $c$ is another absolute constant.

For each $v = (v_i)_{i\in I} \in \{0, 1\}^{I}$ (binary tuples of length $L$ indexed by $I$), we define $\operatorname {sgn}(v) = (-1)^{\sum _{i\in I}v_i}$, and let $u_v\in \mathbb {Z}_n$ be the unique element, by the Chinese remainder theorem, such that

\[ u_v\equiv v_i S_i\, (\mathrm{mod}\,p_i^{\alpha_i})\ \mathrm{for\ all}\ i\in I \quad \mathrm{and} \quad u_v \equiv 0\, (\mathrm{mod}\,p_j^{\alpha_j})\ \mathrm{for\ all}\ j\notin I. \]

Thus, we have the decomposition of $X$ into disjoint copies of translations of $X_0$:

\[ X = \coprod_{v\in \{0, 1\}^I} X_v,\quad \text{where}\ X_v := u_v+X_0. \]

This implies that each $x\in X$ can be written in the form $x = u_v + x_0$ for some $v\in \{0, 1\}^I$ and $x_0\in X_0$. Now we define $\chi : X\to \{1, -1\}$ by $\chi (u_v+x_0) = \operatorname {sgn}(v)\cdot \chi (x_0)$ for all $v\in \{0, 1\}^I, x_0\in X_0$. For any $A\in \mathcal {A}_n$, noting that $A- u_v$ is also in $\mathcal {A}_n$, so

\begin{align*} |\chi(X\cap A)| &= \bigg|\sum_{v\in \{0, 1\}^I} \chi(X_v\cap A)\bigg| = \bigg|\sum_{v\in \{0, 1\}^I} \operatorname{sgn}(v)\cdot \chi_0(X_v\cap A - u_v)\bigg| \\ &\leq \sum_{v\in \{0, 1\}^I} |\chi_0(X_0\cap (A - u_v))| \leq 2^L\max_{A\in \mathcal{A}_n} |\chi_0(X_0\cap A)| \\ &\leq 2^L \cdot c\sqrt{\frac{m}{2^L}} \bigg(L+1+\log\frac{n}{m}\bigg)^{1/2} = c2^{{L}/{2}}\cdot \sqrt{m}\bigg(L+1+\log\frac{n}{m}\bigg)^{{1}/{2}}. \end{align*}

This shows that the coloring $\chi$ satisfies the condition (3.2) on the discrepancy over $\mathcal {A}_n$.

It remains to show (3.3). For each $i\in I$, let $r_i = n/p_i^{\alpha _i - \beta _i} = p_1^{\alpha _1}\cdots p_i^{\beta _i} \cdots p_k^{\alpha _k}$. For any $i\in I$ and any $w\in \mathbb {Z}_n$, we know that $C(r_i, w)$ contains $p^{\alpha _i - \beta _i}$ elements. If $C(r_i, w)\cap X = \emptyset$, then (3.3) trivially holds. It suffices to check $\chi (C(r_i, w)\cap X) = 0$ for $w = \psi _n(t_1,\ldots, t_k)\in X_v$ for some $v\in \{0, 1\}^I$. As $p_j^{\alpha _j}$ divides $r_i$, each element in $C(r_i, w)$ is congruent to $t_j$ mod $p_j^{\alpha _j}$ for $j\ne i$. This implies that $C(r_i, w)$ only has nonempty intersection with $X_v$ and $X_{v'}$ where $v, v'\in \{0, 1\}^I$ differ only at the entry indexed by $i$. Moreover, by the definition of $u$, $u_v - u_{v'}$ is congruent to $0$ mod $p_j^{\alpha _j}$ for all $j\ne i$, and is congruent to $\pm ({s_i}/{2})p_i^{\beta _i}$ mod $p_i^{\alpha _i}$. Thus, $u_v - u_{v'}$ is a multiple of $r_i$, which implies $C(r_i, w) = C(r_i, w) + (u_v - u_{v'})$ or, equivalently $C(r_i, w) - u_v = C(r_i, w) - u_{v'}$. Therefore, we have

\begin{align*} \chi(C(r_i, w)\cap X) &= \chi(C(r_i, w)\cap X_v) + \chi(C(r_i, w)\cap X_{v'}) \\ &= \operatorname{sgn}(v) \cdot \chi_0((C(r_i, w) - u_v)\cap X_0) + \operatorname{sgn}(v') \cdot \chi_0((C(r_i, w) - u_{v'})\cap X_0) = 0. \end{align*}

This is true for all $i\in I$ and $w\in \mathbb {Z}_n$, and thus we conclude that $\chi$ satisfies (3.3) as well.

Proof of Lemma 3.3 Suppose that $n$ has prime factorization $n = p_1^{\alpha _1}\cdots p_k^{\alpha _k}$. For each $1\leq i\leq k$, we partition $\mathbb {Z}_{p_i^{\alpha _i}}$ into $\alpha _i+1$ intervals $(S^{(t)}_{i})_{t=0}^{\alpha _i}$ in the following way. If $p_i = 2$, then we set $S_i^{(\alpha _i)} = \mathbb {Z}_{p_i^{\alpha _i}}$ and $S_i^{(t)} = \emptyset$ for all $0\leq t < \alpha _i$. If $p_i > 2$, then we set $S_i^{(0)} = \{0\}\subseteq \mathbb {Z}_{p_i^{\alpha _i}}$ and $S_i^{(t)} = \{x:p_i^{t-1}\leq x < p_i^t\}$ for $1\leq t\leq \alpha _i$. In particular, we have $|S^{(t)}_i| \leq p_i^{t}$ for all $i$ and $t$. Moreover, for each $i$ and $t > 0$, $S_i^{(t)}$ is always an interval of length $s_ip_i^{t-1}$ in $\mathbb {Z}_{p_i^{\alpha _i}}$ for some even $s_i$.

For each factor $r = p_1^{\delta _1}\cdots p_k^{\delta _k}$ of $n$, we define $Y_r = S_1^{(\delta _1)}\times \cdots \times S_k^{(\delta _k)}\subseteq \mathbb {Z}_{p_1^{\alpha _1}}\times \cdots \times \mathbb {Z}_{p_k^{\alpha _k}}$ and $X_r = \psi _n(Y_r) \subseteq \mathbb {Z}_n$. As each $\mathbb {Z}_{p_i^{\alpha _i}}$ is partitioned into $S_i^{(t)}$ for $0\leq t \leq \alpha _i$, their product is partitioned into $Y_r$ as $r$ ranges over all positive divisors of $n$, so $\mathbb {Z}_n$ is partitioned into $X_r$ as $r$ ranges over all positive divisors of $n$. Because $|S^{(t)}_i| \leq p_i^{t}$ for all $i$ and $t$,

(3.4)\begin{equation} |X_r| = |Y_r| = \prod_{i = 1}^k |S_i^{(\delta_i)}| \leq \prod_{i = 1}^k p_i^{\delta_i} = r. \end{equation}

For each nonempty $X_r$ with $r = p_1^{\delta _1}\cdots p_k^{\delta _k}$, we would like to apply Lemma 3.6 to get a coloring of $X_r$ with bounded discrepancy. Note that we can translate $Y_r$ so that all intervals $S_j^{(\delta _j)}$ for $1\leq j\leq k$ start at $0$, and note those properties from Lemma 3.6 are invariant under translation, so it is applicable to $X_r$. Let $I_r = \{i\in [k]: \delta _i > 0\}\subseteq [k]$. We have that for each $i\in I_r$, $S_i^{(\delta _i)}$ is an interval of length $s_ip_i^{\beta _i}$ for some even $s_i$ and $\beta _i = \delta _i - 1$. This implies that we can find a partial coloring $\chi _r: X_r\to \{-1, 1\}$ such that

(3.5)\begin{equation} \max_{A\in \mathcal{A}_n}|\chi_r(A\cap X_r)| \leq c_02^{{|I_r|}/{2}}\sqrt{|X_r|} \bigg(|I_r| + 1 + \log\frac{n}{|X_r|}\bigg)^{{1}/{2}}, \end{equation}

and for any $i\in I_r$ and any $w\in \mathbb {Z}_n$,

(3.6)\begin{equation} \chi_r(C(n/p_i^{\alpha_i - \beta_i}, w)\cap X_r) = \chi_r(C(n/p_i^{\alpha_i - \delta_i+1}, w)\cap X_r) = 0. \end{equation}

Having defined $\chi _r$ as above for each nonempty $X_r$, we now construct $\chi$ by setting $\chi (x_r) = \chi _r(x_r)$ for each $x_r\in X_r$ for all $r$ that divides $n$. We first show that $\chi$ has low discrepancy over $\mathcal {A}_n$. By (3.4) we have $|X_r| \leq r$. By definition we have $|I_r| \leq k$. In addition, note that $x^{1/2}\cdot (k+1+\log ({n}/{x}))^{ {1}/{2}}$ is increasing for $x\in (0, n]$. Combining these together, we know that for any nonempty $X_r$,

(3.7)\begin{align} 2^{{|I_r|}/{2}}\sqrt{|X_r|}\bigg(|I_r| + 1 + \log\frac{n}{|X_r|}\bigg)^{{1}/{2}} &\leq 2^{{k}/{2}}\sqrt{r}\bigg(k+ 1 + \log\frac{n}{r}\bigg)^{{1}/{2}} \nonumber\\ &\leq 2^{k2}/(k+1)^{1/2} \sqrt{r}\bigg(\log\frac{en}{r}\bigg)^{ 1/2}. \end{align}

Combining (3.5) and (3.7), there exists an absolute constant $c_1$ such that for each nonempty $X_r$,

(3.8)\begin{equation} \max_{A\in \mathcal{A}_n}|\chi_r(A\cap X_r)| \leq c_02^{{k}/{2}}(k+1)^{1/2}\cdot \sqrt{r}\bigg(\log\frac{en}{r}\bigg)^{{1}/{2}} \leq c_12^{({3}/{4})k}\cdot \sqrt{r}\bigg(1 + \log\frac{n}{r}\bigg)^{{1}/{2}}. \end{equation}

This is also true for $X_r = \emptyset$. Moreover, we know that for any $r = p_1^{\delta _1}\cdots p_k^{\delta _k}$,

\[ \sqrt{r}\bigg(1 + \log\frac{n}{r}\bigg)^{{1}/{2}} \leq \prod_{i = 1}^k p_i^{\delta_i/2} \bigg(1 + \log\frac{p_i^{\alpha_i}}{p_i^{\delta_i}}\bigg)^{{1}/{2}} = \sqrt{n} \prod_{i = 1}^k p_i^{-(\alpha_i - \delta_i)/2} (1 + (\alpha_i - \delta_i)\log p_i)^{{1}/{2}}. \]

Summing this over all factors $r = p_1^{\delta _1}\cdots p_k^{\delta _k}$ for $0 \leq \delta _i\leq \alpha _i$, we have that if we set $t_i = \alpha _i - \delta _i$,

\begin{align*} \sum_{r|n}\sqrt{r}\bigg(1 + \log\frac{n}{r}\bigg)^{{1}/{2}} &\leq \sqrt{n} \cdot \sum_{\delta_1 = 0}^{\alpha_1}\cdots \sum_{\delta_k = 0}^{\alpha_k}\prod_{i = 1}^k p_i^{-(\alpha_i - \delta_i)/2} (1 + (\alpha_i - \delta_i)\log p_i)^{{1}/{2}} \\ &= \sqrt{n} \prod_{i = 1}^k \Bigg(\sum_{t_i = 0}^{\alpha_i}p_i^{-t_i/2}(1+t_i\log p_i)^{1/2}\Bigg)\\ &\leq \sqrt{n} \prod_{i = 1}^k \Bigg(\sum_{t_i = 0}^{\infty}p_i^{-t_i/2}(1+t_i\log p_i)^{1/2}\Bigg). \end{align*}

Note that for $p \geq 2$,

\[ f(p) := \sum_{t = 0}^{\infty}p^{-t/2}(1+t\log p)^{1/2} \]

is well-defined and tends to $1$ as $p \to \infty$. Thus, there exists an absolute constant $P > 0$ such that if $p \geq P$, then $f(p) < 2^{{1}/{4}}$. As there are only finitely many prime numbers less than $P$, we conclude that there exists an absolute constant $c_2$ such that

\[ \prod_{i = 1}^k \bigg(\sum_{t_i = 0}^{\infty}p_i^{-t_i/2}(1+t_i\log p_i)^{{1}/{2}}\bigg) = \prod_{i = 1}^k f(p_i) \leq c_2 \cdot 2^{{k}/{4}}. \]

Thus, we have

(3.9)\begin{equation} \sum_{r|n}\sqrt{r}\bigg(1 + \log\frac{n}{r}\bigg)^{{1}/{2}} \leq \sqrt{n}\prod_{i = 1}^k \bigg(\sum_{t_i = 0}^{\infty}p_i^{-t_i/2}(1+t_i\log p_i)^{{1}/{2}}\bigg) \leq c_22^{{k}/{4}}\sqrt{n}. \end{equation}

Thus, for any $A\in \mathcal {A}_n$, by (3.8) and (3.9),

\[ |\chi(A)| = \bigg|\sum_{r|n}\chi_r(A\cap X_r)\bigg| \leq \sum_{r|n}c_12^{{3}/{4}k}\cdot \sqrt{r}\bigg(1 + \log\frac{n}{r}\bigg)^{{1}/{2}} \leq c_1c_22^{k}\sqrt{n}. \]

Here we set $c = c_1c_2$ to obtain the desired bound on the discrepancy over $\mathcal {A}_n$.

Now we study the discrepancy of $\chi$ over $\mathcal {A}_n^0$. Note that $C(r', w) = C(\gcd (r', n), w)$. We may only consider the set of $C(r', w) \in \mathcal {A}_n^0$ for which $r' = p_1^{\gamma _1}\cdots p_k^{\gamma _k}$ is a factor of $n$. By the definition of $\chi$, we have the relation that

(3.10)\begin{equation} \chi(C(r', w)) = \sum_{r|n}\chi_r(C(r', w)\cap X_r). \end{equation}

If $r'$ is not a multiple of $r = p_1^{\delta _1}\cdots p_k^{\delta _k}$, then we know that there exists some $1\leq i\leq k$ for which $\gamma _i \leq \delta _i - 1$. It follows that $\delta _i > 0$, and $i\in I_r$. As $r'$ is a factor of $n$ and $\gamma _i \leq \delta _i - 1$, it is a factor of $n/p_i^{\alpha _i - \delta _i + 1}$. Consequently, the congruence class $C(r', w)$ can be partitioned into congruence classes of the form $C(n/p_i^{\alpha _i - \delta _i + 1}, w')$. Noting that (3.6) holds for any $w'\in \mathbb {Z}_n$, we know that if $r$ is not a factor of $r'$, then $\chi _r(C(r', w)\cap X_r) = 0$. Thus, we can remove all summands on the right-hand side of (3.10) except those $r$ that divides $r'$. We obtain

\[ \chi(C(r', w)) = \sum_{r|r'}\chi_r(C(r', w)\cap X_r) = \chi\bigg(C(r', w) \cap \bigg(\bigcup_{r|r'}X_r\bigg)\bigg). \]

Note that we are taking union over all $r = p_1^{\delta _1}\cdots p_k^{\delta _k}$ for which $0\leq \delta _i \leq \gamma _i$ for all $1\leq i\leq k$. We have

\begin{align*} \bigcup_{r|r'}X_r &= \psi_n\bigg(\bigcup_{r|r'}Y_r\bigg)\\ &= \psi_n\bigg(\bigcup_{\delta_1 = 0}^{\gamma_1} \cdots \bigcup_{\delta_k = 0}^{\gamma_k} S_1^{(\delta_1)}\times \cdots \times S_k^{(\delta_k)}\bigg)\\ &= \psi_n\bigg(\prod_{i = 1}^n \bigg(\bigcup_{\delta_i = 0}^{\gamma_i} S_i^{(\delta_i)}\bigg)\bigg). \end{align*}

From our construction, we know that $\bigcup _{\delta _i = 0}^{\gamma _i} S_i^{(\delta _i)} = \emptyset$ if $p_i = 2$ and $\gamma _i < \alpha _i$, and otherwise

\[ \bigcup_{\delta_i = 0}^{\gamma_i} S_i^{(\delta_i)} = \{x: 0\leq x < p_i^{\gamma_i}\} \subseteq \mathbb{Z}_{p_i^{\alpha_i}}. \]

Thus, we may conclude that

(3.11)\begin{equation} \bigcup_{r|r'}X_r \subseteq \{\psi_n(t_1, \ldots, t_k): 0\leq t_i < p_i^{\gamma_i}\ \mathrm{for\ all}\ \ 1\leq i\leq k\}. \end{equation}

Let $Z_{r'}$ be the set on the right-hand side of (3.11). Any two distinct elements of $Z_{r'}$ differ on some $t_i$ for $1\leq i\leq k$, i.e. they have different remainders when divided by $p_i^{\gamma _i}$ for some $i$. Therefore, their difference is not divisible by $r'$. Hence, there is at most one element of $C(r', w)$ in $\bigcup _{r|r'}X_r \subseteq Z_{r'}$ for any $w\in \mathbb {Z}_n$. We conclude that for any $r'$ that divides $n$ and any $w\in \mathbb {Z}_n$,

\[ |\chi(C(r', w))| = \bigg|\chi\bigg(C(r', w) \cap \bigg(\bigcup_{r|r'}X_r\bigg)\bigg)\bigg| \leq 1. \]

This finishes our proof.

Notation 3 Let $f: \mathbb {Z}_n \to \mathbb {C}$. Any coloring $\chi : \mathbb {Z}_n \to \{1, -1\}$ is a special case. In this section, all summations are over $\mathbb {Z}_n$ unless otherwise specified.

We define the Fourier transform $\widehat f: \mathbb {Z}_n \to \mathbb {C}$ by $\widehat f(r) = \sum _{x\in \mathbb {Z}_n}f(x)e^{- ({2\pi i}/{n})xr}$.

For two functions $f_1, f_2: \mathbb {Z}_n\to \mathbb {C}$, their convolution $f_1*f_2: \mathbb {Z}_n \to \mathbb {C}$ is given by $f_1*f_2(a) = \sum _x f_1(x)f_2(a-x)$. We have the convolution identity $\widehat {f_1*f_2} = \widehat {f_1} \cdot \widehat f_2$.

For any $r\in \mathbb {N}$ that divides $n$, we say that $x \equiv y\ (\mathrm {mod}\,r)$ for $x, y\in \mathbb {Z}_n$ if $x = y + kr$ for some $k\in \mathbb {Z}_n$. We define, for any $r \in \mathbb {N}$ that divides $n$ and $a\in \mathbb {Z}_n$,

\[ g_f(a, r) := \sum_{x\in \mathbb{Z}_n: x\equiv a\, (\mathrm{mod}\,r)} f(x) \quad \mathrm{and} \quad G_f(r) := \sum_{a=0}^{r-1} |g_f(a, r)|^2. \]

We see that $g_f(a, r) = g_f(a+kr, r)$, so $g_f(\cdot, r)$ can be treated as a function on $\mathbb {Z}_r$.

Let $M$ be a set or a multiset of elements in $\mathbb {Z}_n$. For $a, r\in \mathbb {Z}_n$, we define $rM$ to be the multiset $\{rx: x\in M\}$, and $a+M$ to be the multiset $\{a+x: x\in M\}$. We define $m_M$ to be the multiplicity function, i.e. $m_M(x)$ is the multiplicity of $x$ in $M$. In particular, when $M$ is a set, $m_M = 1_M$ is the indicator function. We also define

\[ f(M) = \sum_{x\in M}f(x). \]

Proof. Let $t = n/r$. For each $0\leq k\leq r-1$, we know that by definition

\[ \widehat f(kt) = \sum_{x = 0}^{n-1} f(x)e^{-({2\pi i}/{n})x\cdot kt} = \sum_{x = 0}^{tr-1} f(x)e^{-({2\pi i}/{r})xk} = \sum_{a = 0}^{r-1}g_f(a, r)e^{-({2\pi i}/{r})ak}. \]

Hence, for $g: \mathbb {Z}_r\to \mathbb {C}$ defined by $g(a) := g_f(a, r)$, its Fourier transform is $\widehat g(k) = \widehat f(kt)$. By the Plancherel theorem we have

\[ \sum_{k = 0}^{r-1} \bigg|\widehat f\bigg(k\cdot \frac{n}{r}\bigg)\bigg|^2 = \sum_{k = 0}^{r-1} |\widehat g(k)|^2 = r \sum_{a = 0}^{r-1} |g(a)|^2 = rG_f(r). \]

Proof. We show some properties about the multiplicity function. For the set $M$, we have

(4.2)\begin{equation} f(a+bM) = \sum_{x\in M} f(a+bx) = \sum_x f(x)m_{a+bM}(x) = \sum_x f(x)m_{-bM}(a-x) = f * m_{-bM}(a). \end{equation}

For any $u, v\in \mathbb {Z}_n$, we have

(4.3)\begin{equation} \widehat {m_{-uM}}(v) = \sum_{x} m_{-uM}(x)e^{-({2\pi i}/{n})vx} = \sum_{x\in -uM} e^{-({2\pi i}/{n})vx} = \sum_{y\in -M} e^{-({2\pi i}/{n})vuy} = \widehat{m_{-M}}(uv). \end{equation}

Applying (4.3) twice we have $\widehat {m_{-uM}}(v) = \widehat {m_{-vM}}(u).$ We have

(4.4)\begin{align} \sum_{a}\sum_{b} |f(a+bM)|^2 &= \sum_{b} \sum_a |f * m_{-bM}(a)|^2 = \sum_b \frac{1}{n} \sum_r |\widehat{f * m_{-bM}}(r)|^2 \nonumber\\ &= \frac{1}{n}\sum_b \sum_r |\widehat f(r)|^2\cdot |\widehat {m_{-bM}}(r)|^2 = \frac{1}{n}\sum_b \sum_r |\widehat f(r)|^2 |\widehat {m_{-rM}}(b)|^2 \nonumber\\ &= \sum_r |\widehat f(r)|^2 \cdot \bigg(\frac{1}{n}\sum_b |\widehat {m_{-rM}}(b)|^2\bigg) = \sum_r |\widehat f(r)|^2 \cdot \sum_s |m_{-rM}(s)|^2, \end{align}

where the first equality uses (4.2), the second uses the Plancherel theorem, the third uses the Fourier identity of convolution, the fourth uses (4.3) twice, and the last uses the Plancherel theorem. Now we evaluate $\sum _s |m_{-rM}(s)|^2$. Let $k = \gcd (r, n)$. When $km \leq n$, we know that $rM$ contains $m$ elements with multiplicity 1. Thus, in this case we have

\[ \sum_s |m_{-rM}(s)|^2 = m. \]

Otherwise, when $km > n$, we know that $rM$ contains elements that are multiples of $k$. There are $n/k$ such elements in $\mathbb {Z}_n$. Therefore, by the Cauchy–Schwarz inequality, we have

\[ \sum_s |m_{-rM}(s)|^2 = \sum_{t = 0}^{{n}/{k} - 1} |m_{-rM}(tk)|^2 \geq \frac{\big(\sum_{t = 0}^{{n}/{k} - 1} |m_{-rM}(tk)|\big)^2}{n/k} = \frac{m^2k}{n}. \]

Hence, we may conclude that for any $r \in \mathbb {Z}_n$,

(4.5)\begin{equation} \sum_s |m_{-rM}(s)|^2 \geq \max\bigg(\frac{m^2\cdot \gcd(r, n)}{n}, m\bigg). \end{equation}

Combining this with (4.4), we obtain (4.1).

Proof. For each fixed $b\in \mathbb {Z}_n$, we analyze the summation $\sum _a |f(a+bM)|^2$. Let $r = \gcd (b, n)$ and $k = n/r$. There are two possibilities: $rm \leq n$ or $rm > n$.

If $rm \leq n$, then each element in $bM$ has multiplicity $1$. Therefore, $a + bM$ is a set for all $a\in \mathbb {Z}_n$. Moreover, from our definition of $M = \{0, 1, \ldots, m-1\}$, we know that $a+bM\in \mathcal {A}_n$ is an arithmetic progression in $\mathbb {Z}_n$. In this case, for any $a$, $|f(a+bM)| \leq T_f$, so

(4.7)\begin{equation} \sum_a |f(a+bM)|^2 \leq \sum_a T_f^2 = nT_f^2. \end{equation}

If $rm > n$, i.e. $m > k$, then some elements in $bM$ have multiplicity greater than $1$. The bound in (4.7) no longer applies. Let $K = \{0, 1, \ldots, k-1\}$ and it follows that each element in $bK$ has multiplicity $1$. Moreover, it covers each multiple of $r$ in $\mathbb {Z}_n$ exactly once. Hence,

\[ f(a+bK) = \sum_{t= 0}^{k-1} f(a+bt) = g_f(a, r). \]

Suppose that $m = qk+s$ for integers $q$ and $0\leq s < k$. Then we may write $m_M = m_{S} + \sum _{j = 0}^{q-1} m_{s+jk+K}$ where $S = \{0, 1, \dots, s-1\}$. Thus, for any $a\in \mathbb {Z}_n$, we have

(4.8)\begin{align} f(a + bM) &= f(a + bS) + \sum_{j = 0}^{q-1}f(a+b\cdot (s+jk) + bK) \nonumber\\ &= f(a+bS) + \sum_{j = 0}^{q-1}g_f(a+b\cdot (s+jk), r) = f(a+bS) + q\cdot g_f(a, r). \end{align}

In the last step, we use the fact that $b\cdot (s+jk)$ is a multiple of $r$.

As $s < k$, each element in $bS$ has multiplicity at most $1$, and further $a+bS\in \mathcal {A}_n$ for all $a$. Thus,

(4.9)\begin{equation} |f(a+bS)| \leq T_f. \end{equation}

We now partition $a\in \mathbb {Z}_n$ into congruence classes mod $r$. In particular, we have

(4.10)\begin{equation} \sum_{a}|f(a+bM)|^2 = \sum_{i = 0}^{r-1} \sum_{a\equiv i\, (\mathrm{mod}\,r)} |f(a+bM)|^2. \end{equation}

For each $a'\equiv i\ (\mathrm {mod}\,r)$, there are exactly $s$ choices of $a\equiv i\ (\mathrm {mod}\,r)$ such that $a'\in a+bS$. Thus,

(4.11)\begin{equation} \sum_{j = 0}^{k-1} f(i+jr+bS) =\sum_{a\equiv i\, (\mathrm{mod}\,r)} f(a+bS) = s\cdot g_f(i, r). \end{equation}

Consequently, we have

\begin{align*} \sum_{a\equiv i\, (\mathrm{mod}\,r)} |f(a+bM)|^2 &= \sum_{j = 0}^{k-1} |f(i+jr+bM)|^2 \\ [\textrm{by (4.8)}]\quad &= \sum_{j = 0}^{k-1} |f(i+jr+bS) + q\cdot g_f(i, r)|^2 \\ &= \sum_{j = 0}^{k-1} (|f(i+jr+bS)|^2 + 2 \operatorname{Re}(q\cdot f(i+jr+bS)\overline{g_f(i, r)}) + q^2|g_f(i, r)|^2) \\ [\textrm{by (4.9)}]\quad &\leq kT_f^2 + kq^2|g_f(i, r)|^2 + 2q\operatorname{Re}\bigg(\overline{g_f(i, r)}\sum_{j = 0}^{k-1} f(i+jr+bS)\bigg) \\ [\textrm{by (4.11) }]\quad &= kT_f^2 + kq^2|g_f(i, r)|^2 + 2qs|g_f(i, r)|^2 \\ &\leq kT_f^2 + |g_f(i, r)|^2\cdot \frac{k^2q^2 + 2kqs + s^2}{k} \\ [\textrm{by }m=kq+s]\quad & = kT_f^2 + \frac{m^2}{k}|g_f(i, r)|^2. \end{align*}

Put this into (4.10). We know that in the second case where $rm > n$, i.e. $k < m$,

(4.12)\begin{align} \sum_{a}|f(a+bM)|^2 =\sum_{i = 0}^{r-1} \sum_{a\equiv i\,(\mathrm{mod}\,r)} |f(a+bM)|^2 \leq nT_f^2 + \frac{m^2}{k}G_f(r) = nT_f^2 + \frac{m^2}{k}G_f(n/k). \end{align}

The second case happens exactly when $\gcd (b, n) = n/k$ for some $k < m$ which divides $n$. The number of such choices of $b$ is exactly $\phi (k)$ for any fixed $k$. Hence, combining (4.7) and (4.12), we obtain (4.6).

Proof. By Lemma 4.1, we know that

\[ \frac{n}{k}G_f(n/k) = \sum_{r\in \mathbb{Z}_n: k|r}|\widehat f(r)|^2. \]

Thus, we have (noting that $\sum _{k|l}\phi (k) = l$ for any positive integer $l$)

\begin{align*} \sum_{1\leq k \leq n: k|n} \frac{m^2\phi(k)}{k}G_f(n/k) &= \sum_{1\leq k \leq n: k|n} \frac{m^2\phi(k)}{n}\sum_{r\in \mathbb{Z}_n: k|r}|\widehat f(r)|^2 = \sum_{r\in \mathbb{Z}_n}|\widehat f(r)|^2\cdot \frac{m^2}{n} \sum_{1\leq k\leq n: k|n, k|r}\phi(k)\\ &= \sum_{r\in \mathbb{Z}_n}|\widehat f(r)|^2\cdot \frac{m^2}{n} \sum_{1\leq k\leq n: k|\gcd(n, r)}\phi(k) = \sum_{r\in \mathbb{Z}_n}|\widehat f(r)|^2\cdot \frac{m^2}{n}\gcd(r,n). \end{align*}

Hence, we have the desired equality.

Proof. It suffices to compare the coefficient of each $|\widehat f(r)|^2$ on both sides after expanding all terms of $G_f$ on the right-hand side (4.14) using Lemma 4.1. By Lemma 4.1, for any $k$ that divides $n$,

\[ \frac{n}{k}G_f(n/k) = \sum_{r\in \mathbb{Z}_n: k|r}|\widehat f(r)|^2. \]

For each $r\in \mathbb {Z}_n$, the coefficient $t_r$ of $|\widehat f(r)|^2$ on the right-hand side of (4.14) is given by

\[ t_r = \sum_{1\leq k \leq l: k|\gcd(r, n)}\frac{m^2\phi(k)}{n} + \sum_{l < k \leq n: k|\gcd(r, n)}m = \frac{m^2}{n}\sum_{1\leq k\leq l: k|\gcd(r, n)} \phi(k)+ m\sum_{l < k \leq n: k|\gcd(r, n)}1. \]

If $\gcd (r, n) \leq l$, then we know that the first summation sums over all factors of $\gcd (r, n)$, and the second summation is zero. Hence, we know that in this case,

\[ t_r = \frac{m^2}{n}\gcd(r, n). \]

If $\gcd (r, n) > l$, then in particular the second summation contains at least one term $k = \gcd (r, n)$, and the first summation is nonnegative. Hence, in this case,

\[ t_r > m. \]

We may conclude that $t_r \geq \min ({m^2\cdot \gcd (r, n)}/{n}, m)$ for all $r\in \mathbb {Z}_n$. This yields (4.14).

Proof. For simplicity, let us denote

\[ S_1 := \sum_{1\leq k\leq l: k|n} \phi(k) \quad \mathrm{and} \quad S_2 := \sum_{l < k \leq n: k|n}\frac{1}{k^2}. \]

We aim to show

(4.15)\begin{equation} \operatorname{disc}(\mathcal{A}_n)^2 \geq \frac{1}{({8}/{n})S_1 + 2S_2}. \end{equation}

Because we always have $\operatorname {disc}(\mathcal {A}_n) \geq 1$, we may assume that $S_1 < {n}/{8}$.

Let $\chi : \mathbb {Z}_n \to \{1, -1\}$ be any coloring of $\mathbb {Z}_n$, and let $T_\chi := \max _{A\in \mathcal {A}_n} |\chi (A)|.$ Let $m \leq n$ be a positive integer to be determined later. By Corollary 4.4, we know that

(4.16)\begin{equation} n^2T_\chi^2 + \sum_{1\leq k < m: k|n} \frac{m^2\phi(k)}{k}G_\chi(n/k) \geq \sum_{r\in \mathbb{Z}_n} |\widehat \chi(r)|^2 \cdot \max\bigg(\frac{m^2\cdot \gcd(r, n)}{n}, m\bigg). \end{equation}

By Lemma 4.5, we know that

\[ \sum_{1\leq k \leq n: k|n} \frac{m^2\phi(k)}{k}G_\chi(n/k) = \sum_{r\in \mathbb{Z}_n} |\widehat \chi(r)|^2 \cdot \frac{m^2\cdot \gcd(r, n)}{n}. \]

Subtract both sides from (4.16). We obtain

(4.17)\begin{align} n^2T_\chi^2 + \sum_{r\in \mathbb{Z}_n} |\widehat \chi(r)|^2 \cdot \min\bigg(\frac{m^2\cdot \gcd(r, n)}{n}, m\bigg) \geq \sum_{r\in \mathbb{Z}_n} |\widehat \chi(r)|^2\cdot m + \sum_{m\leq k \leq n: k|n} \frac{m^2\phi(k)}{k}G_\chi(n/k). \end{align}

As $\chi$ takes values in $\{-1, 1\}$, we know that

(4.18)\begin{equation} \sum_{r\in \mathbb{Z}_n}|\widehat\chi(r)|^2 = nG_\chi(n) = n^2. \end{equation}

Note that each $G_\chi (\cdot )$ is nonnegative. By (4.18), the right-hand side of (4.17) is lower bounded by

(4.19)\begin{equation} \sum_{r\in \mathbb{Z}_n} |\widehat \chi(r)|^2\cdot m + \sum_{m\leq k \leq n: k|n} \frac{m^2\phi(k)}{k}G_\chi(n/k) \geq n^2m. \end{equation}

For the left-hand side of (4.17), we apply Lemma 4.6 for $m$ and $l$ and obtain

(4.20)\begin{equation} \sum_{r\in \mathbb{Z}_n} |\widehat \chi(r)|^2 \cdot \min\bigg(\frac{m^2\cdot \gcd(r, n)}{n}, m\bigg) \leq \sum_{1\leq k\leq l:k|n}\frac{m^2\phi(k)}{k}G_{\chi}(n/k) + \sum_{l < k \leq n: k|n} \frac{mn}{k}G_\chi(n/k). \end{equation}

Note that, by definition, each single $g_\chi (a, n/k)$ is the sum of $k$ values of $\chi$. Because $\chi$ takes value in $\{-1, 1\}$, we have

(4.21)\begin{equation} G_\chi(n/k) \leq \frac{n}{k} \cdot k^2 = nk. \end{equation}

Moreover, each $g_\chi (a, n/k)$ is $\chi (A)$ for some $A\in \mathcal {A}_n$, so $|g_\chi (a, n/k)| \leq T_\chi$. This means that for all $k$,

(4.22)\begin{equation} G_\chi(n/k) \leq \frac{n}{k}\cdot T_\chi^2. \end{equation}

We bound the first term on the right-hand side of (4.20) using (4.21) and obtain

(4.23)\begin{equation} \sum_{1\leq k\leq l:k|n}\frac{m^2\phi(k)}{k}G_{\chi}(n/k) \leq m^2n \sum_{1\leq k\leq l:k|n} \phi(k) = nm^2\cdot S_1. \end{equation}

On the other hand, we bound the second term on the right-hand side of (4.20) using (4.22) and obtain

(4.24)\begin{equation} \sum_{l < k \leq n: k|n} \frac{mn}{k}G_\chi(n/k) \leq \sum_{l < k \leq n: k|n} \frac{mn^2}{k^2}T_\chi^2 = n^2mT_\chi^2\cdot S_2. \end{equation}

Put (4.23) and (4.24) into (4.20). We obtain

(4.25)\begin{equation} \sum_{r\in \mathbb{Z}_n} |\widehat \chi(r)|^2 \cdot \min\bigg(\frac{m^2\cdot \gcd(r, n)}{n}, m\bigg) \leq nm^2 \cdot S_1 + T_\chi^2n^2mS_2. \end{equation}

Finally, we put (4.19) and (4.25) into (4.17). We obtain

\[ (n^2 + n^2mS_2)T_\chi^2 \geq n^2m -nm^2 S_1. \]

Dividing both sides by $n^2m$, we obtain

(4.26)\begin{equation} \bigg(\frac{1}{m} + S_2\bigg)T_\chi^2\geq 1 - \frac{m}{n}S_1. \end{equation}

Now we pick $m = \lfloor n/(2S_1)\rfloor$. Note that $S_1 < n/8$ from our assumption, so $m \geq {n}/{4S_1}$. Therefore,

\[ \frac{1}{m} \leq \frac{4}{n}S_1 \quad \mathrm{and} \quad 1- \frac{m}{n}S_1 \geq \frac{1}{2}. \]

Put them into (4.26). We conclude that

\[ T_\chi^2 \geq \frac{1 - ({m}/{n})S_1}{ {1}/{m} + S_2} \geq \frac{1/2}{({4}/{n})S_1 + S_2} = \frac{1}{({8}/{n})S_1 + 2S_2}. \]

As this bound applies to all $T_\chi ^2$, it also applies to $(\operatorname {disc}(\mathcal {A}_n))^2 = \min _{\chi }T_\chi ^2$. Hence, we have (4.15).

Proof. Let $t_1$ be the minimum factor of $n$ that is at least $n^{ 2/3}$, and let $t_2$ be the maximum factor of $n$ less than $n^{ 2/3}$. As

\[ 2\cdot \min\bigg(\sqrt{t_1}, \frac{n}{t_2}\bigg) \geq \min\bigg(\sqrt{t_1}+\frac{n}{t_1}, \sqrt{t_2}+\frac{n}{t_2}\bigg) = \min_{r|n}\bigg(\frac{n}{r} + \sqrt{r}\bigg), \]

it suffices to show that

(4.27)\begin{equation} \operatorname{disc}(\mathcal{A}_n) \geq \frac{1}{4\sqrt{d(n)}}\cdot \min\bigg(\sqrt{t_1}, \frac{n}{t_2}\bigg). \end{equation}

Now we apply Proposition 4.7 to $n$ and $l = {n}/{t_1}$. We bound the two summations as follows. We have

(4.28)\begin{equation} \sum_{1\leq k\leq {n}/{t_1}:k|n} \phi(k) \leq \sum_{1\leq k\leq {n}/{t_1}:k|n} k \leq \frac{n}{t_1}\cdot d(n). \end{equation}

Note that $t_2$ is the largest factor of $n$ less than $t_1$, so the minimum $k$ in $\{{n}/{t_1} < k \leq n: k|n\}$ is $n/t_2$. Thus, we have

(4.29)\begin{equation} \sum_{{n}/{t_1} < k \leq n: k|n} \frac{1}{k^2} \leq \sum_{{n}/{t_2} \leq k \leq n: k|n} \frac{1}{k^2} \leq \frac{t_2^2}{n^2}\cdot d(n). \end{equation}

Using above two bounds, we obtain

\[ (\operatorname{disc}(\mathcal{A}_n))^2 \geq \frac{1}{({8}/{t_1})d(n) + 2{t_2^2}/{n^2}d(n)} \geq \frac{1}{16d(n)}\min\bigg(t_1, \frac{n^2}{t_2^2}\bigg). \]

This is equivalent to (4.27), so we have the expected inequality.

Proof. In Proposition 4.7, we pick $l = p^t$ for some $1\leq t < n$ to be determined later. Note that the factors of $n$ between $1$ and $l$ are given by $s = p^i$ for $0\leq i\leq t$, which are all factors of $l$. Hence, we have

\[ \sum_{1\leq s\leq n: s|n}\phi(s) = l = p^t. \]

All factors of $n$ larger than $l$ are given by $s = p^{i}$ for $t+1\leq i \leq k$. Thus,

\[ \sum_{l < s \leq n: s|n}\frac{1}{s^2} = \sum_{i = t+1}^k p^{-2i} \leq p^{-2t-2}\cdot \bigg(1 + \frac{1}{p^2} + \frac{1}{p^{4}}+ \cdots\bigg) \leq 2p^{-2t-2}. \]

Therefore, by Proposition 4.7 we obtain

\[ \operatorname{disc}(\mathcal{A}_n) \geq \sqrt{\frac{1}{8p^{t-k} + 4p^{-2t-2}}} \geq \frac{1}{4}\cdot \min(p^{({k-t})/{2}}, p^{t+1}) = \frac{1}{4}\cdot p^{\min(({k-t})/{2}, t+1)}. \]

We pick $t = \lfloor {k/3}\rfloor$ to get (4.30).