Let $D(N)$ denote the largest cardinality of a subset of $\{1,\ldots,N\}$ containing no nonzero square difference. While a construction certifying $D(N)\geq (1-o(1))N^{1/2}$ is almost trivial, Erd\H{o}s conjectured that this bound is sharp up to polylogarithmic factors. This was disproved by S\'ark\"ozy and later again by Ruzsa, who found an elegant construction showing that $D(N)\geq c\cdot N^{0.733077\dots}$, with an absolute constant $c>0$. His approach was subsequently refined, leading to the previously best known lower bound with exponent $0.7334117\dots$ due to Beigel-Gasarch and, independently, Lewko. However, in the original paper Ruzsa observed that $3/4$ seems to be the natural barrier of his approach. In this paper we develop a new construction leading to the lower bound \[ \liminf_{N\to\infty}\frac{\log D(N)}{\log N} \geq \alpha_*:= 0.7527964558\ldots; \] thus crossing the natural exponent-$3/4$ barrier of Ruzsa's method. The value $0.7527964558\ldots$ arises from a simple optimisation problem and appears to be the limit of the new approach.
Let $g_n$ be the largest number of Euclidean balls of diameter $1$ which may be needed to cover a set of diameter $1$ in $\mathbb{R}^n$. We study this problem for finite sets invariant under all coordinate permutations. We prove that the exponential growth rate in this symmetric problem can be characterized exactly as a finite-alphabet squared-error rate-distortion supremum $\alpha_0$. Specialized to the two-point case, i.e., for subsets of Boolean cubes, this gives the explicit lower bound \[g_n\ge (1.160235457\ldots-o(1))^n,\] improving the previous best bound $(2/\sqrt3-o(1))^n$. Using Fix's Gaussian characterization of the rate-distortion problem, we give a numerical three-point construction with exponent base greater than $1.160497831$. Finally, we show that $\alpha_0$ is not attained by any finitely supported distribution.
Andrii Arman, A. Bondarenko, A. Prymak et al.· 0 citations
A proper sub-box of $A=\{0,1,2\}^d$ is a product $S_1\times\dots\times S_d$ with each $\varnothing\neq S_i\subsetneq\{0,1,2\}$. A double cover is a finite multiset of proper sub-boxes covering every point of $A$ exactly twice; write $f(d)$ for the minimum size of a double cover. Leader, Milicevic and Tan asked whether $f(d)\ge 2^d$ for all $d$ (Question 4.1 of the PatternBoost paper of Charton-Ellenberg-Wagner-Williamson), analogous to the Alon-Bohman-Holzman-Kleitman partition bound $2^d$. No better than the trivial volume bound was previously known, for any $d\ge 2$. We prove the first nontrivial lower bounds. A modular refinement of the parity argument gives $f(d)\ge 2^{d+1}/(d+1)$; a slicing argument gives $f(4)\ge 19$, $f(5)\ge 33$, both above $2^d$, resolving the question for $d=4,5$ -- the first cases beyond the trivially known $d\le 3$. A finer"line rigidity"argument yields $f(6)\ge 60$, breaking the profile-statistic barrier (capped at $57$, shown here). This is formally verified in Lean 4: $f(6)\ge 60$ is machine-checked on the three standard Mathlib axioms alone. On the upper-bound side, a dimension-lifting construction $f(r+3)\le 6\cdot 2^r+3f(r)$ gives $f(6)\le 81$ (improving the known $82$) and $f(d)\le(\tfrac65+o(1))2^d$ asymptotically; a refinement improves the constant to $\tfrac87$. This makes partial progress on PatternBoost's problem of reducing their constant $1.28$, and refutes the closed-form guess $f(d)=5\cdot 2^{d-2}+1$ from $d=7$ on. Together, $60\le f(6)\le 81$. Finally we isolate the construction-side obstruction -- an"S+c=2^j+1"phenomenon, every skeleton sitting exactly one box past the partition bound -- and show it is of a piece with the Leader-Milicevic-Tan question itself.
We give a random-bit-efficient construction for the inverse star discrepancy. For every fixed $u\in(0,1)$, $k$-wise independent uniform points $\boldsymbol{X}_1,\ldots,\boldsymbol{X}_N$ with $k=O(d(1+\log(1+N/d)))$ satisfy the Monte Carlo bound $D_N^*(\boldsymbol{X}_1,\ldots,\boldsymbol{X}_N) =O(\sqrt{d/N})$ with probability at least $u$. Consequently, $N=O(d\varepsilon^{-2})$ and $k=O(d(1+\log\varepsilon^{-1}))$ suffice to attain discrepancy at most $\varepsilon$. The proof isolates the finitely many moments required by a chaining argument and gives explicit constants. A random vector-valued polynomial over a finite field realizes the required bounded independence on a grid using $O(d^2(1+\log(1+N/d))\log N)$ random bits, rather than the $\Theta(dN\log(dN))$ bits used by independent grid sampling.
A long-standing question posed by Fukuda (1995) and Ziegler (2000) inquires about the asymptotic behavior of $g(n)$, the maximum number of facets that an $n$-dimensional $0/1$-polytope can have. A remarkable result by B\'ar\'any and P\'or (2001) via probabilistic methods established that $g(n)$ is at least superexponential in $n$. In this paper, we propose a drastic change of perspective, which leads us to show that for each $n\geq 10$ there exists a $0/1$-polytope having at least $(n-\lceil 2\log_2 (n)\rceil - 1)!$ facets. This provides a significant improvement over the currently known lower bounds for $g(n)$. Furthermore, when combined with known upper bounds, our construction establishes the asymptotic behavior of $\log g(n)$ up to an error of $O((\log n)^2)$. The methods employed throughout this paper are elementary and fully deterministic. The underlying ideas in our proof stem from the combinatorics of hypersimplices and permutohedra.
Let $F(n)$ be the largest size of a set $A\subseteq[1,n]$ such that $a\nmid bc$ whenever $a,b,c\in A$ and $a\notin\{b,c\}$, with $b$ and $c$ allowed to coincide. We prove \[ F(n)=\pi(n)+\left(\frac{27}{2}+o(1)\right)\frac{n^{2/3}}{(\log n)^2}. \] This determines the second-order constant conjectured by Erd\H{o}s; the upper bound keeps the leading constants in his multiplicative basis, while the lower bound packs scale-separated prime triples by proper edge-colourings.
We study the combinatorial (red-blue) discrepancy of finite point sets with respect to hyperplanes and, more generally, bounded-complexity affine algebraic sets. We prove that every $n$-point set in a real Euclidean space admits a red-blue coloring for which every affine algebraic set of dimension at most $D$ and degree at most $k$ has discrepancy at most $n^{\frac12-\frac{1}{2(D+1)}-\varepsilon}$ for some $\varepsilon=\varepsilon(D,k)>0$. This gives a polynomial improvement over the straightforward VC-dimension bound $\tilde O(n^{\frac12-\frac{1}{2(D+1)}})$. In the opposite direction, we construct $n$-point sets in $\mathbb R^d$ whose discrepancy with respect to hyperplanes is $\tilde\Omega(n^{\frac12-\frac{1}{d+1}}),$ extending the point-line discrepancy lower bound of Chazelle and Lvov. We present further applications of our methods in communication complexity, concerning separation between randomized communication cost and deterministic communication cost with access to equality oracle.