Fugu-MT 論文翻訳(概要): Explicit Nonlinear Functions beyond the Fourier bound

論文の概要: Explicit Nonlinear Functions beyond the Fourier bound

arxiv url: http://arxiv.org/abs/2610.06362v1
Date: Mon, 05 Oct 2026 14:00:30 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-09 08:52:19.058204
Title: Explicit Nonlinear Functions beyond the Fourier bound
Title（参考訳）: フーリエ境界を超える非線形関数の明示
Abstract要約: 高い非線形ベクトル写像を$F: mathbb Fn から mathbb Fm$ へ構築する問題について検討する。具体的には、$F$ と $A = A(m,n)> 0$ を可能な限り小さくしたいので、すべてのアフィン写像 $L: mathbb Fn to mathbb Fm$ に対して、$$mathrmagree(F, L) : | x in mathbb Fn mid F が得られる。
参考スコア（独自算出の注目度）: 0.688204255655161
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: We study the problem of constructing highly nonlinear vectorial maps $F: \mathbb F_2^n \to \mathbb F_2^m$. Concretely, we want an $F$ and an $A = A(m,n)> 0$ as small as possible, so that for every affine map $L: \mathbb F_2^n \to \mathbb F_2^m$ (of the form $L(x) = M x + b $) we have: $$\mathrm{agree}(F, L) := |\{ x \in \mathbb F_2^n \mid F(x) = L(x) \}| \leq A.$$ Such questions have been studied by Nyberg (1991,1993), Carlet and Ding (2004,2007), Liu, Mesnager and Chen (2017), Nagy (2025), and Biryukov, Turecek, and Udovenko (2026). There is a classical method of constructing such functions from bent-functions and Fourier analytic ideas; the best bound achievable by this method is: $$ A(m,n) = Θ(2^{n-m} + 2^{n/2}),$$ and in particular, is never smaller than $2^{n/2}$. In this work, we show how to construct highly nonlinear functions beyond this Fourier bound. Concretely, we show how to construct for every $γ>0$, a function $F: \mathbb F_2^n \to \mathbb F_2^m$ with $m = O_γ(n)$, achieving $$ A(m,n) \leq (1 + γ)^n.$$ Surprisingly, we even achieve the same quantitative behavior for the much harder question of having low agreement with $m$-tuples of degree $d$ polynomials $Q: \mathbb F_2^n \to \mathbb F_2^m$, with $m = O_{γ, d}(n)$. Here the previously best bounds were of the form $A(m,n) = O( 2^{-\frac{n}{2^{d+1}}} \cdot 2^n )$ of Ben-Sasson and Kopparty (2010), based on Gowers-norm-type arguments. All our results generalize to all finite fields $\mathbb F_q$ in place of $\mathbb F_2$. Our methods are based on a new connection to classical results on counting solutions to systems of polynomial equations via algebraic methods. This connection brings us to basic questions in combinatorics, about graphs and hypergraphs with simultaneously a small number of edges and independent sets.
Abstract（参考訳）: F: \mathbb F_2^n \to \mathbb F_2^m$。具体的には、$F$と$A = A(m,n)> 0$を可能な限り小さくしたいので、すべてのアフィン写像 $L: \mathbb F_2^n \to \mathbb F_2^m$ (of the form $L(x) = M x + b $) に対して、$$$\mathrm{agree}(F, L) := |\{ x \in \mathbb F_2^n \mid F(x) = L(x) \}| \leq A が成立する。そのような質問は、Nyberg (1991, 1993), Carlet and Ding (2004, 2007), Liu, Mesnager and Chen (2017), Nagy (2025), Biryukov, Turecek, Udovenko (2026) によって研究されている。そのような関数をベント関数やフーリエ解析のアイデアから構成する古典的な方法があり、この方法によって得られる最良の有界は、$ A(m,n) = シュ(2^{n-m} + 2^{n/2})、$$、特に$が2^{n/2}$より小さいことは決してない。本研究では、このフーリエ境界を超えて高非線形関数を構築する方法を示す。具体的には、すべての$γ>0$に対して、$F: \mathbb F_2^n \to \mathbb F_2^m$ with $m = O_γ(n)$で、$$A(m,n) \leq (1 + γ)^n を達成する方法を示す。驚くべきことに、$m$-tuples of degree $d$ polynomials $Q: \mathbb F_2^n \to \mathbb F_2^m$, with $m = O_{γ, d}(n)$ と低い一致を持つという非常に難しい問題に対して、同じ量的挙動を達成できる。ここで、以前の最良の境界は、ガワーズ-ノルム型の議論に基づいて、$A(m,n) = O( 2^{-\frac{n}{2^{d+1}}} \cdot 2^n )$ of Ben-Sasson and Kopparty (2010) である。すべての結果は、すべての有限体 $\mathbb F_q$ を $\mathbb F_2$ の代わりに一般化する。本手法は代数的手法による多項式方程式系の解の数え上げに関する古典的な結果への新たな接続に基づいている。この接続は、少数のエッジと独立集合を同時に持つグラフとハイパーグラフについて、コンビネータの基本的な疑問をもたらす。

論文の概要: Explicit Nonlinear Functions beyond the Fourier bound

関連論文リスト