Optimal Littlewood-Offord inequalities in groups (Q2338618)

The paper under review proves several Littlewood-Offord type inequalities in arbitrary groups. \textit{J. E. Littlewood} and \textit{A. C. Offord} [Mat. Sb., Nov. Ser. 12(54), 277--286 (1943; Zbl 0061.01801)] proved a bound for the probability that a sum of random signs with non-zero weights hits a point which is asymptotically optimal up to a logarithmic factor. Let \(V_n=\{g_1, \dots, g_n\}\) be a set of non-identity elements of an arbitrary group \(G\), and \(X_i\) be independent random variables that are each distributed on a two-element set \(\{g_i, g_i^{-1}\}\). Define \[\rho (V_n) = \sup_{g\in G} P(X_1\star \cdots \star X_n = g).\] If \(G= (R, +)\) is an additive group of real numbers, then \(X_i = \varepsilon_i\) on \(\{\pm 1\}\) for \(g_i =1\) for all \(i\). The Littlewood-Offord result shows that \(\rho (V_n) = O(\frac{\log n}{\sqrt{n}})\). Using Sperner's theorem from finite set combinatorics, Erdős proved that \(\rho (V_n) \le \frac{{\binom{n}{[n/2]}}}{2^n}\), and this bound is optimal and can be achieved. \textit{J. R. Griggs} [Bull. Am. Math. Soc., New Ser. 28, No. 2, 329--333 (1993; Zbl 0797.11079)] showed a similar optimal bound for finite cyclic groups \(\mathbb Z_m\). For the matrix group \(\mathrm{GL}_d(C)\) with \(m, d, n \ge 2\), \textit{P. H. Tiep} and \textit{V. H. Vu} [Adv. Math. 302, 1233--1250 (2016; Zbl 1346.05295)] proved \(\rho (V_n) \le 141 \max \{\frac{1}{m}, \frac{1}{\sqrt{n}}\}\). \par The authors of the paper under review show that for any \(A \subset G\) with odd or infinite order \[P(X_1\star \cdots \star X_n \in A) \le P(\varepsilon_1+ \cdots + \varepsilon_n \in (-k, k]_m),\] i.e., Theorem 1 holds and is optimal in the case that \(G\) contains an element of order \(m\). For \(g_i\) of order \(\ge m\ge 2\), \(\rho (V_n) \le \frac{2}{m} + \sqrt{\frac{2}{n \pi}} \le 3 \max \{\frac{1}{m}, \frac{1}{\sqrt{n}}\}\). Theorem 1 is proved in Section 3 with a simple group theoretic lemma on countings. The simple random walk on \(\mathbb Z_m\) for odd \(m\) converges to the uniform distribution on \(\mathbb Z_m\) and \[\rho (V_n) = P (\varepsilon_1+ \cdots + \varepsilon_n \in (-1, 1]_m) = (1+ o(1)) \sqrt{\frac{2}{n \pi}} .\] Theorem 3 shows that \(\sup_{g\in G}P (X_i=g) \le \frac{1}{2}\). It is well known that the distribution of the sum of the independent uniform random distribution is asymptotic uniform in \(\mathbb Z_m\) and \(P(X_1\star \cdots \star X_n = g)\le \frac{1}{m} + o(1)\). The proofs follow in the same spirit of \textit{D. J. Kleitman} [Adv. Math. 5, 155--157 (1970; Zbl 0195.40703)] in his solution to the Littlewood-Offord problem in arbitrary dimensions. Section 2 presents an open problem in a conjecture for elements of \(G\) with even orders. The authors hope that Theorem 1 and Theorem 3 hold, in order to complete this problem.