A Note on Sphere Packing Bounds for Tuple Lattice Sieving

• URL: http://arxiv.org/abs/2609.08190v1
• Date: Tue, 08 Sep 2026 03:20:53 GMT
• Title: A Note on Sphere Packing Bounds for Tuple Lattice Sieving
• Abstract summary: A finite set of unit vectors is $k$-irreducible if every signed sum of between two and $k$ distinct elements has norm greater than one.<n>Let $mathcalR_k$ be the maximal rate of such sets, and let $()$ be the maximal rate of spherical codes with pairwise inner products at most $$.
• Score: 0.40611352512781856
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A finite set of unit vectors is $k$-irreducible if every signed sum of between two and $k$ distinct elements has norm greater than one. Let $\mathcal{R}_k$ be the maximal asymptotic rate of such sets, and let $κ(α)$ be the maximal asymptotic rate of spherical codes with pairwise inner products at most $α$. For $k \ge 2$ we show: \begin{align} \mathcal{R}_k \le \min_{1 \le r \le \lfloor k/2 \rfloor} \frac{1}{r} \, κ\!\left(1 - \frac{1}{2r}\right) \, . \end{align} Combining this with standard sphere packing bounds, for large $k$ we obtain an almost-tight asymptotic comparison with the known lower bounds: \begin{align} \left(\tfrac{1}{2}-o(1)\right) \, \frac{\log_2 k}{k} \le \mathcal{R}_k \le (1 + o(1)) \, \frac{\log_2 k}{k} \, . \end{align}

Related papers

• Isospectral majorization and isoperimetric inequalities for coherent states on the Bloch sphere [0.0]
  We prove an isospectral version of Lieb-Solovej inequality.<n>Spherical caps maximize every partial sum of the eigenvalues of Toeplitz operators with symbol $1_$.
  arXiv  Detail & Related papers  (2026-08-12T16:46:26Z)
• Optimal Neural Network Approximation via Empirical Least Squares with Deterministic Samples [7.864201093845001]
  We develop a theory of discrete residual least-squares approximation for elliptic spectral equations $mathfrak L_u=f$ using linearized ReLU$k$ neural networks.<n>We establish a high-probability residual estimate, up to a logarithmic factor and an arbitrarily small smoothness loss.<n>The key analytical ingredient is a Bernstein inequality for linearized ReLU$k$ network spaces.
  arXiv  Detail & Related papers  (2026-08-07T01:22:27Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• MLPs at the EOC: Concentration of the NTK [7.826806223782053]
  We study the concentration of the Neural Tangent (NTK) $K_theta.<n>We prove that an approximate version of gradient independence holds at finite width.<n>Our results imply that in order to accurately approximate the limit, hidden layer widths have to grow quadratically as $m_k = k2 m$ for some $m in bbN+1$ for sufficient concentration.
  arXiv  Detail & Related papers  (2025-01-24T18:58:50Z)
• MLPs at the EOC: Spectrum of the NTK [7.826806223782053]
  We study the properties of the Neuralstyle (NTK) $oversetscriptscriptstyleinftyK.<n>$Delta_phi = fracb2a2+b2$ determines the rate at which the condition number of the NTK matrix converges to its limit as depth increases.
  arXiv  Detail & Related papers  (2025-01-22T21:12:51Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization. Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires. We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
  arXiv  Detail & Related papers  (2024-06-07T08:26:31Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  We construct a dimension-independent k-partite disentangler (like) channel from bipartite unentangled input. We show that to capture NEXP, it suffices to have unentangled proofs of the form $| psi rangle = sqrta | sqrt1-a | psi_+ rangle where $| psi_+ rangle has non-negative amplitudes.
  arXiv  Detail & Related papers  (2024-02-23T12:22:03Z)
• Convergence Rates of Stochastic Zeroth-order Gradient Descent for \L ojasiewicz Functions [6.137707924685666]
  We prove convergence rates of Zeroth-order Gradient Descent (SZGD) algorithms for Lojasiewicz functions. Our results show that $ f (mathbfx_t) - f (mathbfx_infty) _t in mathbbN $ can converge faster than $ | mathbfx_infty.
  arXiv  Detail & Related papers  (2022-10-31T00:53:17Z)
• On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of $\mathbb{R}^N$ [0.24366811507669117]
  Let $mathcalM$ be a compact $d$-dimensional submanifold of $mathbbRN$ with reach $tau$ and volume $V_mathcal M$. We prove that a nonlinear function $f: mathbbRN rightarrow mathbbRmm exists with $m leq C left(d / epsilon2right) log left(fracsqrt[d]V_math
  arXiv  Detail & Related papers  (2022-06-07T15:10:46Z)
• Non-asymptotic spectral bounds on the $\varepsilon$-entropy of kernel classes [4.178980693837599]
  This topic is an important direction in the modern statistical theory of kernel-based methods.<n>We discuss a number of consequences of our bounds and show that they are substantially tighter than bounds for general kernels.
  arXiv  Detail & Related papers  (2022-04-09T16:45:22Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets. Two types of structural assumptions lead to better pseudo-regret bounds.
  arXiv  Detail & Related papers  (2021-03-10T07:33:03Z)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  We study the problem of heavy-tailed mean estimation in settings where the variance of the data-generating distribution does not exist. We design an estimator which attains the smallest possible confidence interval as a function of $n,d,delta$.
  arXiv  Detail & Related papers  (2020-11-24T22:39:21Z)
• A matrix concentration inequality for products [0.0]
  We show that for small enough positive $alpha$, $Z_n$ satisfies the concentration inequality beginequationlabeleq:CTbound mathbbPleft(leftVert Z_n-mathbbEleft[Z_nright]rightVert geq tright) leq 2d2cdotexpleft(frac-t2alpha sigma2 right) quad textfor all
  arXiv  Detail & Related papers  (2020-08-12T04:39:12Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.