Source-linked AI summary
A new upper bound for Sidon sets in $\mathbb{F}_2^{4k+3}$
Darrion Thornburgh
TL;DR
The paper addresses the upper bound on the size of Sidon sets in binary vector spaces. It proves a structural bound for large sets of a particular size congruence, improving the known bound in dimensions n ≥ 7 with n ≡ 3 mod 4. The result also has consequences for distance-5 codes and APN functions.
Problem
For Sidon sets in odd dimensions, the lower- and upper-bound gap remains large, and infinite families of large constructions are lacking.
Source: §1 · p. 2Method
For Sidon sets whose sizes are congruent to 2 modulo 6, the proof bounds points with maximal triple-sum multiplicity and derives a contradiction for sets that are too large.
Source: §1 · p. 2Results
For n ≥ 7 with n ≡ 3 mod 4, the paper improves the best-known upper bound on Sidon-set size by exactly one.
Source: §1 · p. 1Takeaways & Limitations
The result rules out a binary linear distance-5 code family for even t ≥ 4 and establishes APN nonlinearity of at least 3 for even n ≥ 4.
Source: §1 · p. 2The Sidon-set lower- and upper-bound gap remains large, and odd dimensions lack infinite families of large constructions.
Source: §1 · p. 2
Abstract
from arXiv · showhide
A subset $S \subseteq \mathbb{F}_2^n$ is called a Sidon set if no four distinct points of $S$ have zero sum. It is shown that if $n \geq 7$ and $n \equiv 3 \mod 4$, then $|S|\leq 2^{\frac{n+1}{2}}-3$. As a consequence, for any even $t \geq 4$, there does not exist a binary linear $[2^t-3,2^t-2t-2,5]$-code, strengthening a nonexistence result of Brouwer and Tolhuizen from 1993. As a second consequence, we also show that for an even integer $n \geq 4$, every almost perfect nonlinear (APN) function $F \colon \mathbb{F}_2^n \to \mathbb{F}_2^n$ has nonlinearity at least $3$.
1 Introduction
The paper improves the best-known upper bound for Sidon sets by exactly one when n ≥ 7 and n ≡ 3 mod 4. It also derives consequences for binary linear codes and APN-function nonlinearity.
1 Introduction
- For n ≥ 7 with n ≡ 3 mod 4, the paper improves the best-known Sidon-set upper bound by exactly one.Source: §1 · p. 1
- The lower and upper bounds for Sidon-set sizes remain far apart, and odd dimensions lack infinite families of large constructions.Recent improvements in odd dimensions have come from intersections of APN-function graphs with affine hyperplanes.Source: §1 · p. 2
- For |S| ≡ 2 mod 6, the proof bounds points with maximal triple-sum multiplicity and derives a contradiction when |S| is too large.The argument introduces a structural constraint on such Sidon sets and bounds the number of points a for which triples from S sum to a.Source: §1 · p. 2
- The results rule out a binary linear distance-5 code family for even t ≥ 4 and raise the APN nonlinearity lower bound from 2 to 3 for even n ≥ 4.The earlier APN lower bound of 2 is attributed to.Source: §1 · p. 2
2 Notation
This section introduces notation for pair sums, intersections with translates, and triples whose sum is a fixed point. It also records a disjointness property for such triples.
2 Notation
3 Proof of Theorem 1.1
The proof establishes a sharper Sidon-set size threshold by first controlling a structural quantity for sets whose size is 2 modulo 6. It then specializes the threshold to dimensions congruent to 3 modulo 4.
3 Proof of Theorem 1.1
- When |S|≡2 mod 6 and M_S is nonempty, a unique pair s1,s2 is associated with every a in M_S, and |M_S|≤Δ_A(s1+s2).Here A=F_2^n\(S+S).Source: §3 · p. 3
- For distinct s1,s2 in a Sidon set, Δ_D(s1+s2)=2(|S|−2)+6 mult_S,4(s1+s2), where D is the set of pairwise sums.The multiplicity counts 4-point subsets summing to s1+s2.Source: §3 · p. 4
- For |S|>2, the proof reduces its size bound to (|S|+2)^2+8≤2^(n+1).This follows by rearranging the cubic inequality derived in the proof.Source: §3 · p. 5
- For n≥7 with n≡3 mod 4, the proof specializes its general threshold to improve the known upper bound on Sidon-set size.The paper notes that this is a strict improvement for n≥15; n=7 and n=11 already had stronger bounds.Source: §3 · p. 6
4 Connections to coding theory and APN functions
Theorem 1.1 yields two consequences: improved nonexistence results for binary linear codes of minimum distance 5, and a stronger nonlinearity lower bound for APN functions in even dimensions. The APN bound follows by relating the graph of the function to Walsh-transform values.
Coding theory
- For every even t ≥ 4, no binary linear [2^t − 3, 2^t − 2t − 2, 5]-code exists, strengthening Brouwer and Tolhuizen’s result.The coding connection relates nonexistence of particular minimum-distance-5 codes to an upper bound on Sidon-set size.Source: §4 · p. 6
APN functions
- APN means differentially 2-uniform: for each nonzero a and each b, F(x) + F(x + a) = b has at most two solutions.The graph of an APN function is also described as a Sidon set.Source: §4 · p. 6
- The APN argument converts a bound on graph intersections with hyperplanes into a Walsh-transform bound, which yields the nonlinearity conclusion.For even n ≥ 4, the graph cannot intersect a linear hyperplane or its complement in at most two points under the cited Sidon-set bound.Source: §4 · p. 6
- For even n ≥ 4, every APN function has nonlinearity at least 3, improving the previous lower bound of 2.The proof bounds every nonzero Walsh-transform value by 2^n − 6 using the Sidon-set bound.Source: §4 · p. 6