Improved Bounds on Sidon Sets via Lattice Packings of Simplices

Abstract

A $B_h$ set (or Sidon set of order $h$) in an Abelian group $G$ is any subset $\{b_0,b_1,\dots ,b_n\}$ of $G$ with the property that all the sums $b_{i_1}+\cdots +b_{i_h}$ are different up to the order of the summands. Let $\varphi (h,n)$ denote the order of the smallest Abelian group containing a $B_h$ set of cardinality $n+1$. It is shown that \[ \lim_{h \to \infty} \frac{ ϕ(h,n) }{ h^n } = \frac{1}{n! δ_L(\triangle^n)} , \] where ${\delta }_L({△}^n)$ is the lattice packing density of an $n$-simplex in Euclidean space. This determines the asymptotics exactly in cases where this density is known ($n\le 3$) and gives improved bounds on $\varphi (h,n)$ in the remaining cases. The corresponding geometric characterization of bases of order $h$ in finite Abelian groups in terms of lattice coverings by simplices is also given.

9 pages, 2 figures

Cited by in corpus (4)

• Codes in the Space of Multisets---Coding for Permutation Channels with Impairments
• Reconstruction Codes for DNA Sequences with Uniform Tandem-Duplication Errors
• Runlength-Limited Sequences and Shift-Correcting Codes: Asymptotic Analysis
• Lattice Packings of Cross-polytopes from Reed-Solomon Codes and Sidon Sets