Fix integers $0\leq k<n$. Let $F_{n,k}(N)$ be the least size of a finite set $B\subset\Z^n$ that contains a filled axis-parallel cube $k$-skeleton centered at each point of some $N$-point set. We prove that $F_{n,k}(N)$ has order $N^{1-(n-k)/(2n^2)}$, with constants depending only on $n$ and $k$. Thornton proved the upper bound and lower bounds with every smaller exponent; the endpoint lower bound was open for $k\geq1$. For square boundaries in $\Z^2$, the exponent is $7/8$. A midpoint count and Shearer's inequality handle large radii; induction in lattice cells handles small radii.
For practical $N$ let $h(N)$ be the least $k$ such that every integer $1\le m\le N$ is a sum of at most $k$ distinct divisors of $N$. We prove $h(n!)\le(2\log2+o(1))\,n/\log n$. This improves the bounds of order $n/(\log n)^{1/2-\varepsilon}$ established in Tenenbaum-Yokota's Lemma 4 and Yokota's 1995 knapsack note. We combine their decreasing greedy construction with the sharper factorial divisor-gap estimate of Berend-Harmse. Counting the steps separately below and above $\sqrt{n!}$, with the upper range handled through reciprocal divisors, retains the leading coefficient in the gap exponent and yields the explicit constant $2\log2$.
Let $S_k(\alpha;K)$ denote the exponential sum over $k$-free integers in the short interval $(N-K,N]$. For $s>0$, we prove essentially tight bounds on the $s$-th moments of $S_k(\alpha;K)$ whenever $K \gg N^{\theta_{k,s}+\epsilon}$ for some $\theta_{k,s}<1/2$. As an immediate consequence, we obtain a lower bound for the $L^1$-mean of the M\"obius-twisted exponential sum over short intervals of length at least $N^{0.49685}$. Moreover, we show that further improvements on all of these results would follow immediately from improvements to an $\ell^2$-estimate involving the M\"obius function.
Let $F(n)$ be the number of rectangles, not necessarily axis-parallel, whose vertices belong to the $n\times n$ square grid of lattice points. We compute the complete table $F(1),\ldots,F(N)$ exactly in $O(M(N)\log N)$ coefficient-ring operations and $O(N\log N)$ ring elements of working memory, where $M(N)$ is a regular bound for multiplying degree-$N$ polynomials. The ring-level statement assumes that $6$ is invertible; over $\mathbb Z$ the only division is instead performed exactly in the elementary boundary term. With quasi-linear polynomial multiplication the arithmetic bound is $O(N\log^2 N)$. The algorithm applies a square-root cover before coefficient extraction and evaluates the resulting rational wedge and triangular sums by a local-denominator divide-and-conquer recursion. Primitive directions are recovered coefficientwise by M\"obius inversion, followed by five prefix sums. A modular number-theoretic-transform (NTT) implementation with certified Chinese-remainder (CRT) recovery is evaluated experimentally against the $O(N^{3/2})$ all-values algorithm.
Dmitry A. Babichev, D. Pinchuk· arXiv.org· 1 citation
Fix positive integers $N,k,n$ with $n\ge k$. We seek the minimum number of members of size at least $n$ in a finite family of finite sets closed under union and containing exactly $N$ distinct sets of size $k$. This problem is a specialization of the Leck--Roberts--Simpson weighted conjecture: assign weight one to sets of size at least $n$ and zero to smaller sets. The predicted minimizer consists of the unions of nonempty subfamilies of the first $N$ $k$-subsets of the natural numbers, ordered by their largest elements and, when these agree, by their increasing lists lexicographically. For an integer $t\ge 1$, call the range \[ \binom{n+t-1}{k}<N\le\binom{n+t}{k} \] the $t$-th strip. We prove the layered conjecture throughout the first strip, and throughout the second strip for $k=3$. For arbitrary $k$, we prove the second strip for families of subsets of an $(n+2)$-element set. For $k,t\ge 3$, we prove the $t$-th strip for families of subsets of an $(n+t)$-element set whenever $n\ge(t+1)(k-1)$. With no restriction on the ground set, we prove it for $k\ge 3$ and $t\ge 2$ whenever $n>\frac{5}{2} k^2t$. For sufficiently large $k$, we obtain a sufficient bound of order $k^2t/\log k$, uniformly in $t\ge2$.
For positive integers $d$ and $k$, let $n_k(d)$ be the maximum order of a graph of maximum degree at most $d$ and diameter at most $k$. We prove that $$ \lim_{d\to\infty}\frac{n_k(d)}{d^k}=1$$ for every fixed $k$, thereby resolving the asymptotic degree-diameter problem for fixed diameter and proving a conjecture of Bollob\'as. The lower bound comes from regular graphs $H_{k,q}$, indexed by prime powers $q$, whose vertices are partial flags in $\mathbb{F}_q^{\,2k+1}$. These graphs have diameter $k$ and order $|V(H_{k,q})| =(1+o(1))\Delta(H_{k,q})^k$. We also construct, for every fixed $\ell \ge 2$, graphs of maximum degree at most $d$ and line-graph diameter at most $\ell$ with $(1+o(1))d^{\ell}$ edges.
W. Cames van Batenburg, Samuel Korsky· 0 citations
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
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
