title: A nonuniform Littlewood-Offord inequality for all norms
authors: Kyle Luh David Xiang
text: 
  	Optimal minimal-perturbation university
   timetabling with faculty preferences
      
  Jakob KotasDepartment of Mathematics, University of Portland, 5000 N Willamette Blvd, Portland OR 97203 USA; kotas@up.edu [Corresponding author] Peter PhamShiley School of Engineering, University of Portland, 5000 N Willamette Blvd, Portland OR 97203 USA; phamp23@up.edu, koellman23@up.edu Sam Koellmann[2]
      December 30, 2023
  =======================================================================================================================================================================================================================================================================================================================
  
  
  		Let _i be vectors in ^d and {_i} be independent Rademacher random variables.  Then the Littlewood-Offord problem entails finding the best upper bound for sup_∈^d(∑_i _i = ).  
  		Generalizing the uniform bounds of Littlewood-Offord, Erdős and Kleitman, a recent result of Dzindzalieta and Juškevičius provides a non-uniform bound that is optimal in its dependence on _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 ^d, not just the ℓ_2 norm.  This resolves a conjecture of Dzindzalieta and Juškevičius. 
  	
  	
  	
  	
  
  § INTRODUCTION
  
  	Let {_k}_k=1^n be independent Rademacher random variables (i.e. (_k = 1) = 1/2 and (_k = -1) = 1/2).  We let R_n denote the sum of these random variables.  In their study of random polynomials, Littlewood and Offord <cit.> encountered the following problem.  What is the best bound on (∑_i=1^n a_i _i = x) with |a_i| ≤ 1.  Littlewood and Offord established that max_x (∑ a_i _i = x) = O(log n/ n^1/2) for all a_i such that |a_i| ≤ 1.  <cit.>.  With a short, insightful argument, Erdős <cit.> established the optimal bound 
  	
      ρ() :=max_x (∑_i=1^n a_i _i = x ) ≤n⌊ n/2 ⌋/2^n = O(n^-1/2).
  
  	
  	
  	The results of Littlewood, Offord and Erdős attracted the attention of many researchers and numerous variants of the Littlewood-Offord problem have been proposed and investigated.  Erdős and Moser showed that an improved bound held when all the a_i are distinct <cit.>.  Later, Sárkőzy and Szemerédi obtained the optimal bound for distinct a_i.  Many more results were obtained when considering more complex arithmetic structure of the a_i's <cit.>.  
  	In a different direction, Erdős conjectured that a result analogous to (<ref>) should hold in in higher dimensions.  This extension was non-trivial and it took two decades before such a result was verified by Kleitman <cit.>.
  	 
  		Let d ∈ℕ and _i ∈^d with _i_2 ≤1 and _i ≠ 0.  Then,
  		
      ρ(_1, …, _n) := sup_∈^d(∑_i=1^n _i _i = ) ≤n⌊ n/2 ⌋/2^n.
   
  	
  	Inspired by the inverse problems of additive combinatorics, Tao and Vu began a line of work to known as inverse Littlewood-Offord  theorems which attempt to explain when ρ() is large <cit.>.  Essentially, they showed that ρ() is large only when the entries of  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 <cit.>.  This theory and its variants played an important role in estimating the singularity probability of random matrices (see <cit.> and the references therein). 
  	
  	In another vein of work, Tiep and Vu <cit.> obtained a Littlewood-Offord-type inequality in the setting of non-commutative groups and Juškevičius and Š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  that an adversary can change to force ρ() to be large <cit.>. 
  	
  	Recently, Dzindzalieta and Juškevičius established a non-uniform Littlewood-Offord inequality in all dimensions.  The bound is non-uniform in that it incorporates information about the vector .
  	 
  		Let _i ∈^d with _i_2 ≤ 1 and _i ≠ 0 for all i ∈ [n].  Then,
  		
      (∑_i=1^n _i _i = ) ≤(R_n = k + δ_n,k) = n⌈n+k/2⌉/2^n.
  
  		where k = ⌈_2 ⌉ and 
  		
      δ_n,k = 
      		
      		1     n+k  is even
      
      		0    otherwise.
  
  	
  	This result is optimal in n and _2 as can be seen by setting _i = (_2/k + δ_n,k, 0 , …, 0).  In <cit.>, it was conjectured that the result should hold for any norm on ^d, not just the ℓ_2 norm.  
  	
  	 <cit.> 
  		Let · be an arbitrary norm on ^d.  Let _i ∈^d be such that _i≤ 1 and _i ≠ 0 for all i ∈ [n].  Then,
  		
      ( ∑_i _i = ) ≤(R_n = k + δ_n,k).
  
  	
  	In <cit.>, they used a rotation argument to reduce the multi-dimensional case to the one dimensional case.  However, their rotation only preserves the ℓ_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 <cit.> and prove Conjecture <ref>.
  	 
  		Let · be an arbitrary norm on ^d.  Let _i ∈^d be such that _i≤ 1 and _i ≠ 0 for all i ∈ [n].  Then,
  		
      ( ∑_i _i = ) ≤(R_n = k + δ_n,k).
  
  		where k = ⌈⌉ and 
  		
      δ_n,k = 
      		
      		0     n+k  is even
      
      		1    otherwise.
  
  	
  	
  	
  	
  
  § ACKNOWLEDGEMENTS
  
  	We thank Victor Reis and Aleksei Kulikov for pointing out an error in our first draft.  We also thank Aleksei for suggesting the perturbation argument at the end of the note.    
  	
  	
  
  § AUXILIARY RESULTS
  
  	We will make use of the following one dimensional non-uniform Littlewood-Offord bound.
  	 <cit.>
  		For non-zero a_i ∈ such that |a_i|≤ 1, we have that
  		
      (∑_i=1^n _i a_i = x) ≤(R_n = k + δ_n,k)
  
  		where k = ⌈ |x| ⌉.
  	
  	
  	We will also utilize the basic theory of dual norms.  
  	
  		Let · be a norm on ^d.  Let ·_* denote the dual norm where for any ∈^d,
  		
      _* = sup{⟨, ⟩: ≤ 1}
   
  		where ⟨·, ·⟩ is the standard inner product on ^d.
  	
  	We then have a basic Cauchy-Schwarz type inequality.  We include the elementary proof for the reader's convenience.  
  	
  	 
  		Let · be a norm on ^d and ·_* be its dual.  Then, for , ∈^d,
  		
      |⟨, ⟩| ≤_*
  
  	
  	
  	
  		Let = /.  Then we have
  		
      ⟨, ⟩   = ⟨, ⟩
         ≤_*.
  
  		To include the absolute value, we apply the same argument to -.  
  	
  	
  	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.
  	 (e.g. <cit.>)
  		Let · be a norm on ^d.  Then, for ∈^d,
  		
      = _**.
   
  	
  	
  	
  	
  
  § PROOF OF THEOREM <REF>
  
  	
  		For any ∈^d, we have that
  		
      (∑_i=1^n _i _i = ) ≤(⟨∑_i=1^n _i _i, ⟩ =  ⟨, ⟩)
  
  		
  		In particular, if we let = argmax__*≤ 1⟨, ⟩, we can conclude that
  		
      (∑_i=1^n _i _i = )    ≤(⟨∑_i=1^n _i _i, ⟩ =  ⟨, ⟩) 
         = (∑_i=1^n  ⟨_i, ⟩_i =  _**) .
  
  		
  		Since ≤ 1 by assumption, Lemma <ref> implies that
  		
      |⟨_i, ⟩ | ≤_i_*  ≤ 1
  .  
  		
  		Therefore, we can apply Proposition <ref>, so
  		
      ( ∑_i _i = ) ≤(R_n = k + δ_n,k)
  
  		where k = ⌈_**⌉ = ⌈⌉.  This final equality follows from Lemma <ref>.  In our application of Proposition <ref>, we implicitly assumed that ⟨_i, ⟩≠ 0.  To ensure this, we can simply choose a small perturbation of  such that ⌈⟨, ⟩⌉ =  ⌈_**⌉.  
  	
  	
  	
  	
  	
  	abbrv
  	
  	
  	
  	
  