Exact Five-Class Paley Offsets and Sharper Nonlinearity Bounds Exceeding the Patterson-Wiedemann Direct-Sum Threshold

Building directly on the recent breakthrough of Tang and Maitra (IACR ePrint 2026/2680), which established the first explicit fixed-dimension improvement over the Patterson-Wiedemann direct-sum nonlinearity bound at n = 375, we prove an elementary closed-form five-class offset theorem for unmodified translated quadratic-residue templates S = c + sgn(a)R over every prime q = 3 (mod 4) with n = ord_q(2) = (q-1)/2 odd. Evaluating the Reis-Song potential directly on the unmodified template S = 3 - R at n = 375 (q = 751) sharpens the certified threshold from C = 1.193239 to C = 1.192508, yielding NL(f) > 2^(n-1) - 442096 * 2^((n-39)/2) = N_BC(n) + 82192 * 2^((n-39)/2) for every odd n >= 375 (both unbalanced and balanced), enlarging the margin above the Patterson-Wiedemann direct-sum bound from 2^((n-39)/2) to 272 * 2^((n-39)/2) with zero label exchanges. An exhaustive check over all 140,625 single exchanges confirms local optimality at n = 375, whereas at n = 431 (q = 863) two potential-guided exchanges further sharpen the constant from C = 1.184952 to C = 1.183620 (gain > 85487 * 2^((n-39)/2)). Complete Hensel-Cornacchia screening of all 208 prime-order index-two candidates in 375 <= n <= 5000 yields an explicit monotone hierarchy passing 2^(n-1) - 26 * 2^((n-11)/2) for all odd n >= 743 (q = 1487) and 2^(n-1) - 24 * 2^((n-11)/2) for all odd n >= 4935 (q = 9871), closing 69.38% of the normalized gap to Schmidt's asymptotic limit. We also establish the flat-spectrum index threshold q >= 713 for single-coset Reis-Song feasibility and report Stickelberger-LLL evaluations below n = 375. Includes the compiled PDF manuscript and a reproducible verification package (LaTeX source and pure-rational Python verification scripts).

Authors

Publication Details

Journal
Figshare
Published
2026-11-21
DOI
https://doi.org/10.6084/m9.figshare.35082409
Primary Topic
Coding theory and cryptography
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Exact Five-Class Paley Offsets and Sharper Nonlinearity Bounds Exceeding the Patterson-Wiedemann Direct-Sum Threshold

Valéria Gonzaga dos Santos, André Oliveira Naufel de Toledo, Filipe Vono
Figshare
Coding theory and cryptography
preprint

Exact Five-Class Paley Offsets and Sharper Nonlinearity Bounds Exceeding the Patterson-Wiedemann Direct-Sum Threshold

Valéria Gonzaga dos Santos, André Oliveira Naufel de Toledo, Filipe Vono
preprint en

Abstract

Building directly on the recent breakthrough of Tang and Maitra (IACR ePrint 2026/2680), which established the first explicit fixed-dimension improvement over the Patterson-Wiedemann direct-sum nonlinearity bound at n = 375, we prove an elementary closed-form five-class offset theorem for unmodified translated quadratic-residue templates S = c + sgn(a)R over every prime q = 3 (mod 4) with n = ord_q(2) = (q-1)/2 odd. Evaluating the Reis-Song potential directly on the unmodified template S = 3 - R at n = 375 (q = 751) sharpens the certified threshold from C = 1.193239 to C = 1.192508, yielding NL(f) > 2^(n-1) - 442096 * 2^((n-39)/2) = N_BC(n) + 82192 * 2^((n-39)/2) for every odd n >= 375 (both unbalanced and balanced), enlarging the margin above the Patterson-Wiedemann direct-sum bound from 2^((n-39)/2) to 272 * 2^((n-39)/2) with zero label exchanges. An exhaustive check over all 140,625 single exchanges confirms local optimality at n = 375, whereas at n = 431 (q = 863) two potential-guided exchanges further sharpen the constant from C = 1.184952 to C = 1.183620 (gain > 85487 * 2^((n-39)/2)). Complete Hensel-Cornacchia screening of all 208 prime-order index-two candidates in 375 <= n <= 5000 yields an explicit monotone hierarchy passing 2^(n-1) - 26 * 2^((n-11)/2) for all odd n >= 743 (q = 1487) and 2^(n-1) - 24 * 2^((n-11)/2) for all odd n >= 4935 (q = 9871), closing 69.38% of the normalized gap to Schmidt's asymptotic limit. We also establish the flat-spectrum index threshold q >= 713 for single-coset Reis-Song feasibility and report Stickelberger-LLL evaluations below n = 375. Includes the compiled PDF manuscript and a reproducible verification package (LaTeX source and pure-rational Python verification scripts).

Figshare
Coding theory and cryptography
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Exact Five-Class Paley Offsets and Sharper Nonlinearity Bounds Exceeding the Patterson-Wiedemann Direct-Sum Threshold — Valéria Gonzaga dos Santos, André Oliveira Naufel de Toledo, et al. · Figshare (2026) | TGRS Research Map | TGRS