CS Paper Radar

A new upper bound for Sidon sets in $\mathbb{F}_2^{4k+3}$

Darrion Thornburgh

cs.IT math.CO ·submitted 2026-09-23 11:45 UTC · v1
theory

Abstract

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$.

Comment
7 pages

Closest papers

Nearest neighbours by meaning across the whole index.

The Walsh spectrum of the Dobbertin APN function

cs.IT math.CO ·2026-11-13 ·Lukas Kölsch
similarity 0.62
Abstract · 27 pages

APN functions yield the best resistance to differential attacks when used as a building block of a block cipher. APN functions induced by monomials over finite fields have received particular interest both for their simplicity and their unique properties. A key property of APN functions is their linearity, which has been determined for all known APN monomials outside of the Dobbertin APN monomials. In this paper, we close this gap and determine the complete Walsh spectrum and in particular the linearity of the Dobbertin APN monomial, answering a problem that has been open for more than 20 years. Using known connections, our result also yields the asymptotically largest Sidon sets in elementary abelian $2$-groups constructed so far as well as binary linear codes of minimum distance $5$ that are almost optimal.

0.25

Exact Minimum Extension Degrees for Reed Solomon Codes under Linear and Nonlinear Repair at the Cut Set Bound

cs.IT ·2026-10-25 ·Yuhan Li
theoryhot direction similarity 0.61
Abstract · 21 pages

We study the minimum extension degree required for a Reed--Solomon code to admit exact $\mathbb{F}_q$-linear repair at the cut-set bound from every prescribed set of $d$ helpers. Let $s=d-k+1$, and let $Q_s(n)$ be the minimum product of $n$ pairwise coprime integers, each at least $s$. For every prime power $q$ and all $3\le k<d<n\le2d-2$, we prove that the minimum degree over $\mathbb{F}_q$ is exactly $sQ_s(n)$. When all surviving nodes are helpers, we also characterize the admissible extension degrees and bound the number of coordinates that can attain the cut-set bound. The required achievability follows from existing construction methods; we give a short existence proof using splitting subspaces. For a family of parameters with $n>2d-2$, we obtain strictly smaller extension degrees, showing that the range restriction cannot be omitted altogether. Finally, we prove that a nonlinear repair scheme attaining the cut-set bound induces an $\mathbb{F}_p$-linear repair scheme on the same code, where $p$ is the characteristic. Consequently, the extension-degree lower bounds over the prime field remain valid without a linearity assumption.

0.51

Quadratic APN Functions of $\mathbb{F}_2^{10}$ with a Self-Equivalence of Prime Order

cs.IT cs.CRmath.CO ·2026-11-13 ·Emanuele Bellini
similarity 0.61
Abstract

Almost perfect nonlinear (APN) functions of $\mathbb{F}_2^n$ have the lowest possible differential uniformity. The only known APN permutation in even dimension, in dimension six, is equivalent to a quadratic APN function with a nontrivial linear self-equivalence; no APN permutation is known for even $n \geq 8$. In a published collection of about 3.8 million quadratic APN classes of dimension eight, at most 0.34% have a nontrivial linear self-equivalence. In dimension ten, the 25 literature classes considered here all have one. We study all quadratic APN functions of $\mathbb{F}_2^{10}$ with such a self-equivalence, which usually confines them to a much smaller linear space. Up to conjugacy and power similarity, self-equivalences of prime order have 299 types. We settle 298 of them. Elementary lemmas exclude 280 types, and exhaustive searches confirm this for 242 of them. The other 18 types are settled by exhaustive searches with exact equivalence certificates. Up to extended affine equivalence, the 298 types contain 29 classes of quadratic APN functions, four of them new. This also classifies the quadratic APN functions with coefficients in a subfield. Exactly 24 classes contain one with coefficients in $\mathbb{F}_4$, and all 3 that contain one with coefficients in $\mathbb{F}_{32}$ are among them. The open type consists of the quadratic canonical triplicate functions. They correspond to maximum additive Hermitian rank-distance codes. Three different searches find only the invariants of 16 classes, all among the 29. We conjecture there are no others. No quadratic APN function in the 298 settled types is Carlet-Charpin-Zinoviev equivalent to a permutation.

0.24

Deep holes of full-length Reed--Solomon codes: uniform bounds and exact classifications

cs.IT math.COmath.NT ·2026-10-22 ·Xiang Fan
hot direction similarity 0.61
Abstract · 43 pages

Let $u$ be a received word for the full-length Reed--Solomon code $\operatorname{RS}_q(k)$, with interpolation polynomial $f_u$ of degree $k+m$. For each $m\in\{3,4,5,6,7\}$, we classify all such deep holes over every finite field, without a field-size hypothesis. None occur for odd $m$ in this range. At $m=4$ and $m=6$, the only exceptions are, respectively, the Segre sextic and Frobenius-power families; these occur only in dimension two over fields of characteristic two. For arbitrary $m\geqslant3$, we also establish two uniform bounds. If $\sqrt q\geqslant12(m+1)\log(2m+2)$, no word of interpolation degree $k+m$ is a deep hole when $q$ is odd, $k\geqslant3$, or $m$ is odd. If $q>16(m+2)^4$, we obtain the corresponding complete classification at every admissible $k$, including the explicit dimension-two exceptions. Our proofs use an agreement criterion expressed in complete homogeneous symmetric functions, agreement-count estimates, finite geometry, permutation-polynomial restrictions, and subset constructions for solving the resulting symmetric-function equations. The remaining finite cases are settled by finite computations with supplied certificates and deterministic verification programs.

0.51

Reduced APN permutations and a disproof of the Galois-ring lifting conjecture

cs.IT math.NT ·2026-08-31 ·Daniele Bartoli, Pantelimon Stanica
similarity 0.60
Abstract

We construct infinite families of reduced almost perfect nonlinear (APN) permutations of $\mathbb{F}_{2^m}$ that admit coefficientwise permutation lifts to $\mathrm{GR}(2^k,m)$ for every $k>1$. These families disprove Conjecture~2 of Rønjom and Sandrib (Cryptogr. Commun., 2026), even for reduced polynomial representatives. For every odd $m\ge5$ with $3\nmid m$, we obtain explicit seven-term polynomials over $\mathbb{F}_2$ with formal derivative identically one. We derive them from a complete criterion for the reduced representative of $A(x)^{2^s+1}$ to have no critical point in $\mathbb{F}_{2^m}$, where $A$ is an invertible linearized polynomial and $\gcd(s,m)=1$. We then apply the cube case to construct a second family of degree $2^{m-1}+2$, whose nonconstant derivatives avoid zero by an explicit trace identity. A fixed parameter in $\mathbb{F}_{32}$ gives this family in every dimension $m=5r$ with $r$ odd, including a degree-$18$ example over $\mathbb{F}_{32}$. Both constructions remain in Gold linear equivalence classes, so liftability of reduced representatives is not invariant under invertible $\mathbb{F}_2$-linear input changes. We obtain the lifting conclusions from the standard Galois-ring permutation criterion. We also verify a degree-$24$ example supplied by Zhang and Haobo, prove a trace-adjoint criterion for reduced quadratic functions, and interpret the derivative condition through ramification at rational points.

0.44

There is no binary linear $[65,9,29]$ code

cs.IT cs.DMmath.CO ·2026-11-18 ·Zhichao Tang, Xiang Fan
theory similarity 0.60
Abstract · 10 pages

We prove that no binary linear $[65,9,\geqslant29]$ code exists, equivalently, that no even binary linear $[66,9,\geqslant30]$ code exists. Together with known constructions, this determines $d_2(65,9)=28$, $n_2(9,29)=66$, and $n_2(9,30)=67$. A residual-code bound and a known construction also give $d_2(122,10)=56$. To prove nonexistence, we associate with a hypothetical even code a quadratic function derived from half the codeword weight modulo $2$. Its polar form determines the fourth derivative of a Boolean function of degree at most four. Character sums, weight moments, and the exclusion of weight-$42$ codewords give upper bounds on the support of this function in seven cases. Restrictions to nondegenerate affine subspaces exclude six cases. In the remaining case, equality would force four distinct coordinate functionals to be identically $1$ on an affine seven-space, although at most two can have this property. The argument uses published minimum-length results for binary linear codes of dimensions eight and nine.

0.25

Optimal Ordering-Free Two-Dimensional Insdel Reed-Solomon Codes via Cross-Ratios

cs.IT ·2026-11-16 ·Runqing Qiu, Shixin Zhu, Yang Li, San Ling
similarity 0.59
Abstract · 16 pages

Insertion-deletion (insdel) codes correct synchronization errors. By the half-Singleton bound, an ${[n,2]}_q$ code has minimum insdel distance at most $2n-4$. The smallest field size of two-dimensional Reed--Solomon (RS) codes attaining this bound is $Θ(n^3)$. Unlike the minimum Hamming distance, the minimum insdel distance of an RS code depends on the ordering of its evaluation points. An evaluation set is called ordering-free if every ordering of its points gives an RS code attaining the half-Singleton bound. In this paper, we first show that for $n\ge6$ every ${[n,2]}_q$ code attaining the half-Singleton bound is an RS code, and hence $q\ge\binom{n}{3}+2$. Secondly, we show that an ordering-free evaluation set with $n\ge6$ points in $\mathbb{F}_q$ satisfies $n<q^{1/3}+2$, and that it has at most $r+1$ points if $q=r^3$ for a prime power $r\ge3$. Finally, by using cross-ratios, we construct an ordering-free evaluation set with $r+1$ points in $\mathbb{F}_{r^3}$ for every prime power $r$. Hence, the bound $r+1$ is attained for $r\ge3$. Moreover, the constructed set is even robust against permutations combined with insdel errors.

0.14

On the MDS conjecture in even characteristic

cs.IT math.CO ·2026-10-20 ·Bocong Chen, Jing Huang
theoryhot direction similarity 0.59
Abstract · 34 pages

We prove that every nontrivial linear $[n,k]$ maximum distance separable (MDS) code over a finite field $\F_q$ of characteristic two satisfies $n\le q+1$, except in dimensions $k=3$ and $k=q-1$, where $n\le q+2$. This resolves the linear MDS conjecture in even characteristic.

0.24