The Koml\'os conjecture is a classic problem in discrepancy theory; it asks whether an absolute constant $K$ exists such that given any $n$ vectors $a_1,\ldots,a_n$ inside the $m$-dimensional Euclidean ball, regardless of how large $m,n$ are, there is always a selection of signs $\varepsilon_1,\ldots,\varepsilon_n$ guaranteeing $$\|\varepsilon_1a_1+\ldots+\varepsilon_na_n\|_\infty \leq K.$$ We show that if the $\varepsilon_i$'s are allowed to take not just the values of $\pm 1$ but any unit modulus complex number, which we refer to as complex discrepancy, then the above inequality holds for a finite, explicit constant $K_{\mathbb{C}}$. Here, the $\ell^\infty$ norm of the resulting vector in $\mathbb{C}^m$ is the largest modulus of its entries, and thus the complex discrepancy of real vectors is equivalent to their rank-$2$ vector discrepancy. Therefore, our result resolves the Koml\'os problem for Gaussian discrepancy -- a discrepancy measure introduced by Chewi, Gerber, Rigollet and Turner. Our paper builds upon the recent work of Bansal and Jiang on the Beck-Fiala and Koml\'os conjectures, which we approach from the formalism of Burkholder and the Bellman function method from probability and harmonic analysis. Our work was in part motivated by the realization that the complex discrepancy of the columns of any unitary matrix is equal to 1, a fact that follows from a straightforward calculation based on Idel and Wolf's generalization of the Sinkhorn normal form for unitary matrices.
Let $X$ be a smooth complex projective variety of dimension $n$, and let $L$ be an ample Cartier divisor. We prove that $K_X+mL$ is globally generated for every integer $m\geq\lceil C_0n\rceil$, where $C_0=1.77629\ldots$ is an explicit constant. In particular, $K_X+2nL$ is globally generated. We also prove that if $Z$...
A deterministic algorithm that finds signs with $\|A\varepsilon\|_\infty<99$ using $O(mn+n^{\omega+2}\log^3 n)$ arithmetic operations, where $\omega>2$ is any fixed attainable matrix-multiplication exponent; with the current bounds on $\omega$ this is $\widetilde O(mn+n^{4.372})$.
A subset $A\subseteq \mathbb N_0$ is $k$-AP covering if there exists a constant $n_0$ such that for every integer $x>n_0$, there exists $d\in\mathbb N_0$ such that $x-d, x-2d,\dots,x-(k-1)d$ are all in $A$. Disproving a conjecture of Kiss, S\'andor, and Yang, we prove that for every integer $k\geq 6$, there exists a co...
We obtain a Furstenberg-S\'ark\"ozy-type result for sets $A\subset [N]$ whose difference set $A-A$ does not contain the sum of $s$-many $k$-th powers of positive integers, with $k>1$ odd and $s>0$ even. Namely, we prove that such sets must satisfy a power-saving bound $|A| \, \ll \, N^{1-\frac1k\min\{s \, \sigma_k, \,...
Alexandros Kalogirou, Andrew Lott, Á. Magyar et al.· 1 citation
The classical Thompson's conjecture asserts that in any finite nonabelian simple group $G$, there exists a conjugacy class $S$ whose square is equal to the entire group. Shalev (Annals Math., 2009) conjectured that a much stronger quantitative version holds: there exists $\epsilon>0$ such that for any conjugacy class $...
For $m\geq 2$, let $c_p(m)$ be the all-dimensional best constant in $$ \left\|\sum_{k=1}^m A_k\right\|_p \leq c_p(m)\left\|\sum_{k=1}^m |A_k|\right\|_p. $$ Tang and Zhang conjectured an explicit formula for every finite $p>1$. We disprove the conjecture with two explicit real $2\times 2$ rank-one matrices at $p=3/2$. T...