For a fixed integer $t\geq 3$, consider families of $t$-mark Golomb rulers whose positive-difference sets are pairwise disjoint and contained in $[1,U]$. Let $P_t(U)$ be the largest number of integers covered by such a family. We determine the threshold for asymptotically complete coverage: \[ P_t(U)=U-o(U) \quad\Longleftrightarrow\quad 3\leq t\leq 5. \] The cases $t=3,4$ follow from the known existence spectra for perfect difference families. For $t=5$, Wild's product construction, in the form recorded by Mathon and applied to perfect families of orders $121$ and $161$, gives a multiplicative semigroup of exact-covering scales; an elementary density lemma on its logarithms then supplies a scale $(1-o(1))U$ below every sufficiently large $U$. For the converse, we give a self-contained one-frequency Fourier obstruction. If $x_0\in(\pi,3\pi/2)$ is the first positive solution of $\tan x=x$ and \[ \gamma_0=-\frac{2\sin x_0}{x_0}=0.4344672564\ldots, \] then, for every fixed $t\geq 6$, \[ \liminf_{U\to\infty}\left(1-\frac{P_t(U)}{U}\right) \geq \frac{(t-1)\gamma_0-2}{2(t-2)}. \] In particular, the forced gap for six-mark rulers is at least $2.1542035\%$. We also prove a discrete small-difference bound which yields a stronger obstruction for every $t\geq14$ and forces a gap of \[ \frac12-\frac1{\sqrt t}-\frac7{8t}+O(t^{-3/2}) \] as $t\to\infty$.
Wegner conjectured that every finite family $\mathcal R$ of axis-parallel rectangles satisfies $\tau(\mathcal R)\le 2\nu(\mathcal R)-1$, where $\nu$ is the packing number and $\tau$ is the piercing number. Ajwani, Gajjala, Raman, and Ray recently disproved this by constructing a triangle-free counterexample on $2196\cdot 8^9$ rectangles and, using a computer-assisted package-and-port recursion, obtained a standard LP gap of $17891/8064$ for Maximum Independent Set of Rectangles. We give a simpler and hand-checkable counterexample with $64$ rectangles. It is built from an eight-rectangle gadget whose independent sets inject into four ordered slots; we then use four horizontal and four vertical copies of this gadget to form a triangle-free family with $\nu=16$ and $\tau\ge 32$. We use the same horizontal-vertical step to define recursive families of rectangles $P_r$ with $\nu(P_r)=4^{2^r}$. For the standard clique, equivalently point, relaxation we obtain a finite gap $73/32$ at $P_3$, improving the previous benchmark of $17891/8064$. We then construct recursive fractional solutions and matching piercing sets showing $\lim_r \alpha^*(P_r)/\nu(P_r)=\lim_r \tau(P_r)/\nu(P_r)=5/2$. Finally, by disjoint union with isolated rectangles, we show that every rational $t\in[1,5/2)$ occurs as a standard LP gap and also as a packing-piercing ratio for suitable rectangle families.
For $c>1$ and an integer radix $b\ge2$, we study the positive integers $m$ for which $mb^k\le c^m<(m+1)b^k$ for some $k\ge0$; for integer $c$, this is the self-prefix leading-digit condition. We derive an exact shrinking-target criterion; for $c\ge2$, an exact signed-discrepancy identity isolates both infinitude and the conjectural logarithmic count. For $c\ge2$ with nonintegral logarithmic slope, Lambert $W_{-1}$ inversion produces a candidate sequence with an eventual two-gap law and an exact counting formula; for $(c,b)=(2,10)$ all consecutive candidate gaps are $3$ or $4$. For algebraic $c$ with irrational $\log_b c$, the Lambert-root phases satisfy deterministic moving-target asymptotics in an explicit nontrivial power range strictly below the critical scale. For irrational logarithmic slope, actual hits obey fixed-difference and arithmetic-chain rigidity; for multiplicatively independent integer parameters, coherent endpoint hits at floor resonance centers force every intermediate term. Finally, set $\rho=\{\log_b c\}$. For fixed multiplicatively independent integers $c,b$, an interpolated continued-fraction locator has bit complexity $O(N^{1-1/\nu}\operatorname{polylog}N)$ for every $\nu>\mu(\rho)$. We give an explicit certified instance for $(2,10)$, whose infinitude remains open.
We consider the following problems: Given two $n \times n$ tables defining binary operations $+$ and $\cdot$ on a set $S$ of $n$ elements, decide whether $(S,+,\cdot)$ forms a ring or, respectively, a field. Recently, Dudek, Fischer, Gokaj, Jin, K\"unnemann, Mao, and Redzic (STOC 2026) obtained the following two (near-)optimal results: (1) A randomized $O(n^2\log(1/\delta))$-time algorithm for verifying rings. (2) A deterministic $O(n^2)$-time algorithm for verifying fields. Their algorithms build on machinery of Evra, Gadot, Klein, and Komargodski (FOCS 2024), which relies on Classification of Finite Simple Groups (CFSG). In this work, we give a deterministic $O(n^2)$-time algorithm for ring verification, resolving the deterministic complexity of this problem. As a corollary, we also obtain a deterministic $O(n^2)$-time algorithm for field verification. Our algorithms are elementary and avoid CFSG machinery entirely.
We exhibit two explicit circulant graphs of prime order $251$ that are $K_4$-free and have independence number $19$. Consequently \[R(4,20)\ge 252.\] These improve the bound $R(4,20)\ge 237$ given by Nagda, Raghavan, Thakurta and the long standing bound $R(4,21)\ge 242$ recorded in Radziszowski's dynamic survey. The graphs are $32$-subsets of a pair of undirected quintic cyclotomic classes modulo $251$, in analogy with the quartic-residue circulant of order $313$ used for $R(4,22)$. Clique-freeness is elementary; the independence-number claims are certified by a bitset branch-and-bound on the $186$-vertex residual of a vertex.
Let $L$ be a fixed set of positive integers. A family $\mathcal{F}\subseteq 2^{[n]}$ is called $L$-differencing if $\lvert A\setminus B\rvert\in L$ for every ordered pair of distinct members $A,B\in\mathcal{F}$. A longstanding conjecture of Frankl, proposed in 1985, asserts that every $L$-differencing family has size at most $\binom{n}{|L|}$. We resolve this conjecture asymptotically for every fixed $L$, and obtain the exact answer in the only case in which the conjectured bound could be tight. (1) If $L\ne [s]$ and $n$ is large, then every $L$-differencing family satisfies $\lvert \mathcal{F}\rvert \le \left(\frac{s}{s+1}+o_L(1)\right)\binom{n}{s}$. (2) If $L=[s]$ and $n\ge 2s-1$, then $\lvert \mathcal{F}\rvert\le\binom{n}{s}$, with equality only for $\binom{[n]}{s}$ and $\binom{[n]}{n-s}$. The first result follows by reducing directed differences to restricted Hamming distances. For the exact result, we develop a new homogeneous polynomial method, which might be of independent interest.
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