\begin{document}

	\title{A nonuniform Littlewood-Offord inequality for all norms}
	
	\begin{abstract}
		Let $\mathbf{v}_i$ be vectors in $\mathbb{R}^d$ and $\{\varepsilon_i\}$ be independent Rademacher random variables.  Then the Littlewood-Offord problem entails finding the best upper bound for $\sup_{\mathbf{x} \in \mathbb{R}^d} \mathbb P(\sum \varepsilon_i \mathbf{v}_i = \mathbf{x})$.  
		Generalizing the uniform bounds of Littlewood-Offord, Erd\H{o}s and Kleitman, a recent result of Dzindzalieta and Ju\v{s}kevi\v{c}ius provides a non-uniform bound that is optimal in its dependence on $\|\mathbf{x}\|_2$.  In this short note, we provide a simple alternative proof of their result.  Furthermore, our proof demonstrates that the bound applies to any norm on $\mathbb{R}^d$, not just the $\ell_2$ norm.  This resolves a conjecture of Dzindzalieta and Ju\v{s}kevi\v{c}ius. 
	\end{abstract}
	
	
	\section{Introduction}
	Let $\{\varepsilon_k\}_{k=1}^n$ be independent Rademacher random variables (i.e. $\mathbb P(\varepsilon_k = 1) = 1/2$ and $\mathbb P(\varepsilon_k = -1) = 1/2$).  We let $R_n$ denote the sum of these random variables.  In their study of random polynomials, Littlewood and Offord \cite{LO1943roots} encountered the following problem.  What is the best bound on $\mathbb P(\sum_{i=1}^n a_i \varepsilon_i = x)$ with $|a_i| \leq 1$.  Littlewood and Offord established that $\max_x \mathbb P(\sum a_i \varepsilon_i = x) = O(\log n/ n^{1/2})$ for all $a_i$ such that $|a_i| \leq 1$.  \cite{LO1943roots}.  With a short, insightful argument, Erd\H{o}s \cite{erdos1945LO} established the optimal bound 
	\begin{equation} \label{eq:erdosLO}
	\rho(\mathbf{a}) :=\max_x \mathbb P\left(\sum_{i=1}^n a_i \varepsilon_i = x \right) \leq \frac{\binom{n}{\lfloor n/2 \rfloor}}{2^n} = O(n^{-1/2}).
	\end{equation}
	
	
	The results of Littlewood, Offord and Erd\H{o}s attracted the attention of many researchers and numerous variants of the Littlewood-Offord problem have been proposed and investigated.  Erd\H{o}s and Moser showed that an improved bound held when all the $a_i$ are distinct \cite{erdos1947moser}.  Later, S\'ark\H{o}zy and Szemer\'edi obtained the optimal bound for distinct $a_i$.  Many more results were obtained when considering more complex arithmetic structure of the $a_i$'s \cite{stanley1980distinct, halasz1977combinatorial, rv2008invertibility}.  
	In a different direction, Erd\H{o}s conjectured that a result analogous to \eqref{eq:erdosLO} should hold in in higher dimensions.  This extension was non-trivial and it took two decades before such a result was verified by Kleitman \cite{kleitman1966combinatorial}.
	\begin{theorem} 
		Let $d \in \mathbb{N}$ and $\mathbf{v}_i \in \mathbb{R}^d$ with $\|\mathbf{v}_i\|_2 \leq1$ and $\mathbf{v}_i \neq 0$.  Then,
		\[
		\rho(\mathbf{v}_1, \dots, \mathbf{v}_n) := \sup_{\mathbf{x} \in \mathbb{R}^d} \mathbb P\left(\sum_{i=1}^n \varepsilon_i \mathbf{v}_i = \mathbf{x} \right) \leq \frac{\binom{n}{\lfloor n/2 \rfloor}}{2^n}.
		\] 
	\end{theorem}
	Inspired by the inverse problems of additive combinatorics, Tao and Vu began a line of work to known as \emph{inverse} Littlewood-Offord  theorems which attempt to explain when $\rho(\mathbf{a})$ is large \cite{taovu2009ILO}.  Essentially, they showed that $\rho(\mathbf{a})$ is large only when the entries of $\mathbf{a}$ reside in a generalized arithmetic progression.  Many results in this direction followed and culminated in the optimal inverse Littlewood-Offord theorems of Nguyen and Vu \cite{nguyen2011optimal}.  This theory and its variants played an important role in estimating the singularity probability of random matrices (see \cite{taovu2009ILO, rv2008invertibility, ferber2019counting, tikhomirov2020bernoulli} and the references therein). 
	
	In another vein of work, Tiep and Vu \cite{tiep2016nonabelian} obtained a Littlewood-Offord-type inequality in the setting of non-commutative groups and Ju\v{s}kevi\v{c}ius and \v{S}emetulskis obtained optimal bounds for arbitrary groups.  Bandeira, Ferber and Kwan proposed a new perspective and investigated a resilience version of the Littlewood-Offord problem, namely the number of coefficients in $\mathbf{a}$ that an adversary can change to force $\rho(\mathbf{a})$ to be large \cite{bandeira2017resilience}. 
	
	Recently, Dzindzalieta and Ju\v{s}kevi\v{c}ius established a non-uniform Littlewood-Offord inequality in all dimensions.  The bound is non-uniform in that it incorporates information about the vector $\mathbf{x}$.
	\begin{theorem} \label{thm:l2}
		Let $\mathbf{v}_i \in \mathbb{R}^d$ with $\|\mathbf{v}_i\|_2 \leq 1$ and $\mathbf{v}_i \neq 0$ for all $i \in [n]$.  Then,
		\[
		\mathbb P(\sum_{i=1}^n \varepsilon_i \mathbf{v}_i = \mathbf{x}) \leq \mathbb P(R_n = k + \delta_{n,k}) = \frac{\binom{n}{\lceil \frac{n+k}{2} \rceil}}{2^n}.
		\]
		where $k = \lceil \|\mathbf{x}\|_2 \rceil$ and 
		\[
		\delta_{n,k} = 
		\begin{cases}
		1 & n+k \text{ is even} \\
		0 & \text{otherwise}. 
		\end{cases}
		\]
	\end{theorem}
	This result is optimal in $n$ and $\|\mathbf{x}\|_2$ as can be seen by setting $\mathbf{v}_i = (\frac{\|\mathbf{x}\|_2}{k + \delta_{n,k}}, 0 , \dots, 0)$.  In \cite{dzindzalieta2020nonuniform}, it was conjectured that the result should hold for any norm on $\mathbb{R}^d$, not just the $\ell_2$ norm.  
	
	\begin{conjecture} \cite[Conjecture 2]{dzindzalieta2020nonuniform} \label{conj:main}
		Let $\|\cdot \|$ be an arbitrary norm on $\mathbb{R}^d$.  Let $\mathbf{v}_i \in \mathbb{R}^d$ be such that $\|\mathbf{v}_i\| \leq 1$ and $\mathbf{v}_i \neq 0$ for all $i \in [n]$.  Then,
		\[
		\mathbb P\left( \sum \varepsilon_i \mathbf{v}_i = \mathbf{x} \right) \leq \mathbb P(R_n = k + \delta_{n,k}).
		\]
	\end{conjecture}
	In \cite{dzindzalieta2020nonuniform}, they used a rotation argument to reduce the multi-dimensional case to the one dimensional case.  However, their rotation only preserves the $\ell_2$ norm and so their argument only applies to this norm.  
	In this short note, we provide an alternate proof of the main result in \cite{dzindzalieta2020nonuniform} and prove Conjecture \ref{conj:main}.
	\begin{theorem} \label{thm:main}
		Let $\|\cdot \|$ be an arbitrary norm on $\mathbb{R}^d$.  Let $\mathbf{v}_i \in \mathbb{R}^d$ be such that $\|\mathbf{v}_i\| \leq 1$ and $\mathbf{v}_i \neq 0$ for all $i \in [n]$.  Then,
		\[
		\mathbb P\left( \sum \varepsilon_i \mathbf{v}_i = \mathbf{x} \right) \leq \mathbb P(R_n = k + \delta_{n,k}).
		\]
		where $k = \lceil \|\mathbf{x}\| \rceil$ and 
		\[
		\delta_{n,k} = 
		\begin{cases}
		0 & n+k \text{ is even} \\
		1 & \text{otherwise}. 
		\end{cases}
		\]
	\end{theorem}
	
	
	
\section{Auxiliary Results}
	We will make use of the following one dimensional non-uniform Littlewood-Offord bound.
	\begin{proposition} \cite{dzindzalieta2020nonuniform}\label{prop:1d}
		For non-zero $a_i \in \mathbb{R}$ such that $|a_i|\leq 1$, we have that
		\[
		\mathbb P(\sum_{i=1}^n \varepsilon_i a_i = x) \leq \mathbb P(R_n = k + \delta_{n,k})
		\]
		where $k = \lceil |x| \rceil$.
	\end{proposition}
	
	We will also utilize the basic theory of dual norms.  
	\begin{definition}
		Let $\|\cdot\|$ be a norm on $\mathbb{R}^d$.  Let $\|\cdot \|_*$ denote the dual norm where for any $\mathbf{u} \in \mathbb{R}^d$,
		\[
		\|\mathbf{u}\|_* = \sup\{ \langle \mathbf{u}, \mathbf{x} \rangle: \|\mathbf{x}\|\leq 1\}
		\] 
		where $\langle \cdot, \cdot \rangle$ is the standard inner product on $\mathbb{R}^d$.
	\end{definition}
	We then have a basic Cauchy-Schwarz type inequality.  We include the elementary proof for the reader's convenience.  
	
	\begin{lemma} \label{lem:inequality}
		Let $\|\cdot\|$ be a norm on $\mathbb{R}^d$ and $\|\cdot \|_*$ be its dual.  Then, for $\mathbf{x}, \mathbf{y} \in \mathbb{R}^d$,
		\[
		|\langle \mathbf{x}, \mathbf{y} \rangle| \leq \|\mathbf{x}\| \|\mathbf{y}\|_*
		\]
	\end{lemma}
	
	\begin{proof}
		Let $\mathbf{v} = \mathbf{x}/\|\mathbf{x}\|$.  Then we have
		\begin{align*}
		\langle \mathbf{x}, \mathbf{y} \rangle &= \|\mathbf{x}\| \langle \mathbf{v}, \mathbf{y} \rangle \\
		&\leq   \|\mathbf{x}\| \|\mathbf{y}\|_*.
		\end{align*}
		To include the absolute value, we apply the same argument to $-\mathbf{x}$.  
	\end{proof}
	
	Additionally, we will make use of the standard fact that in finite-dimensional spaces, the double dual norm is the same as the original norm.
	\begin{lemma} (e.g. \cite[Theorem 1.11.9]{megginson2012introduction})\label{lem:doubledual}
		Let $\|\cdot\|$ be a norm on $\mathbb{R}^d$.  Then, for $\mathbf{x} \in \mathbb{R}^d$,
		\[
		\|\mathbf{x} \| = \|\mathbf{x}\|_{**}.
		\] 
	\end{lemma}
	
	
	\section{Proof of Theorem \ref{thm:main}}
	\begin{proof}
		For any $\mathbf{y} \in \mathbb{R}^d$, we have that
		\[
		\mathbb P\left(\sum_{i=1}^n \varepsilon_i \mathbf{v}_i = \mathbf{x} \right) \leq \mathbb P\left(\left\langle \sum_{i=1}^n \varepsilon_i \mathbf{v}_i, \mathbf{y} \right\rangle =  \langle \mathbf{x}, \mathbf{y} \rangle\right)
		\]
		
		In particular, if we let $\mathbf{y} = \text{argmax}_{\|\mathbf{u}\|_*\leq 1} \langle \mathbf{x}, \mathbf{u}\rangle$, we can conclude that
		\begin{align*}
		\mathbb P\left(\sum_{i=1}^n \varepsilon_i \mathbf{v}_i = \mathbf{x} \right) &\leq \mathbb P\left(\left\langle \sum_{i=1}^n \varepsilon_i \mathbf{v}_i, \mathbf{y} \right\rangle =  \langle \mathbf{x}, \mathbf{y}\rangle \right) \\
		&= \mathbb P\left(\sum_{i=1}^n  \left\langle  \mathbf{v}_i, \mathbf{y} \right\rangle \varepsilon_i =  \|\mathbf{x}\|_{**} \right) .\\
		\end{align*}
		
		Since $\|\mathbf{v}\| \leq 1$ by assumption, Lemma \ref{lem:inequality} implies that
		\[\left|\left\langle  \mathbf{v}_i, \mathbf{y} \right\rangle \right | \leq \|\mathbf{v}_i\| \|\mathbf{y}\|_*  \leq 1\].  
		
		Therefore, we can apply Proposition \ref{prop:1d}, so
		\[
		\mathbb P\left( \sum \varepsilon_i \mathbf{v}_i = \mathbf{x} \right) \leq \mathbb P(R_n = k + \delta_{n,k})
		\]
		where $k = \lceil \|\mathbf{x}\|_{**} \rceil = \lceil \|\mathbf{x}\| \rceil$.  This final equality follows from Lemma \ref{lem:doubledual}.  In our application of Proposition \ref{prop:1d}, we implicitly assumed that $\langle  \mathbf{v}_i, \mathbf{y} \rangle \neq 0$.  To ensure this, we can simply choose a small perturbation of $\mathbf{y}$ such that $\lceil \langle \mathbf{y}, \mathbf{x} \rangle \rceil =  \lceil \|\mathbf{x}\|_{**} \rceil$.  
	\end{proof}
	
	
	
	
	

	

	

\end{document}