New Extension of the Weil Bound for Character Sums
New extension of the Weil bound for
character sums,
and applications to coding
Tali Kaufman (Bar-Ilan)
Shachar Lovett (IAS)
FOCS, October 2011
Talk overview
•
Weil bound for character sums
•
Our new extension for the Weil bound
•
Application: testing of affine invariant codes
•
Proof overview
•
Open problems
Character sums
@+a+
+%=?
Weil bound for character sums
•
Formal way of saying:
Low-degree polynomials are either:
-
very structured; or
-
behave like random functions
•
Extremely useful tool in
–
Number theory, analysis, algebra,…
–
Explicit constructions, derandomization, lower
bounds,
coding theory
,…
Additive characters
•
– finite field
•
Additive character
: map
such that
•
Example: prime field
•
Example: non-prime field
Weil bound for character sums
•
f(x) -
degree d polynomial
over
•
additive character
•
Then either
(1) is
constant
for all
or
(2) is
“uniformly distributed”
Weil bound: examples
•
Example 1:
squares are “uniform” in
•
Example 2:
f(x) lies in a subspace of co-dim 1
c≠0,
Weil bound for character sums
•
f(x)
degree d polynomial
•
is constant; or
•
Many generalizations:
–
Multi-variate polynomials (Deligne), polynomials
on curves (Bombieri),…
•
Main limitation
: useful only when
Going beyond root field size
•
We can go beyond
degree
if we restrict
ourselves to
sparse polynomials
•
Bourgain: Let f(x) be a
sparse polynomial
of
degree
.
Then either is constant or
Going beyond root field size
•
We consider polynomials over (or )
–
Degree
of x
e
is e
–
Weight degree
of x
e
is the
hamming weight
of e
(equiv: degree as n-variate polynomial over )
•
We show: Let f(x) be a
sparse polynomial
of
low weight degree
.
Then either is constant or
Going beyond root field size
•
Consider polynomials over (or )
–
Degree
of x
e
is e
–
Weight degree
of x
e
is the
hamming weight
of e
(equiv: degree as polynomial over )
•
We show: Let f(x) be a
sparse polynomial
of
low weight degree
.
Then either is constant or
Bourgain: sparsity ~log(n)
This work: sparsity n
0.1
(assumes d=O(log n))
Good subcodes of Reed-Muller
•
Reed-Muller code: multivariate polynomials in
of
degree d
•
Equivalently: univariate polynomials in
of
weight degree d
•
We show: For
d=O(log n)
, sub-code of
sparse
polynomials with n
0.1
monomials
forms a (non-
linear) code with near optimal distance
Going beyond root field size
•
We can actually show a stronger result,
combining Weil bound with sparse polynomials
•
Let f(x)=g(x)+h(x) where
–
g(x) has
degree
–
h(x) is
sparse
,
low weight degree
Then either is constant or
Character sums
in coding theory
@+a+
+%=!
Locally testable codes
•
Codes where codewords can (whp) be verified
to be (nearly) correct with only a few queries
•
Combinatorial heart of many PCP
constructions
•
Big question: can locally testable codes form
“good codes” (constant rate & distance)
Locally testable codes
•
Constructions:
–
Hadamard [BLR]
–
Polynomials [Alon-Kaufman-Krivelevich-Litsyn-
Ron, Arora-Sudan, Samorodnitsky, Raz-Safra,
Moshkovitz-Raz,…]
–
Combinatorial [Dinur-Goldenberg, Imagliazzo-
Kabanets-Wigderson,…]
Locally testable codes
•
General families of codes which guarantee local
testability:
–
Near orthogonal codes [Kaufman-Litsyn]
–
Random sparse codes [Kaufman-Sudan, Kopparty-
Saraf]
–
Sparse affine invariant codes
[Grigorescu-Kaufman-
Sudan]
•
We show: slightly less sparse affine invariant
codes are still locally testable
Affine invariant codes
•
Codeword: function
•
Code: linear subspace
•
Code is
affine invariant
if it is invariant under
affine transformations of the input, i.e.
Testing of affine invariant codes
•
Grigorescu-Kaufman-Sudan:
Any affine invariant code
with
exp(n) codewords (i.e. sparse)
can be locally testable with O(1) queries
•
Use Bourgain character sum estimate for
sparse polynomials
Testing of affine invariant codes
•
This work:
Any affine invariant code
with
exp(n
1+
)
codewords (slightly less sparse)
can be locally testable with poly(n
) queries
•
Use the fact that our character sum estimate
works for
slightly less sparse polynomials
Proof overview
@+a+
+%=!!
Main theorem
•
f(x)=g(x)+h(x) polynomial over
–
g(x) has degree
–
h(x)
sparse polynomial
of
low weight degree
•
Then either is constant or
Main proof ideas
•
Use derivatives + convexity to reduce degrees and wt deg
•
f(x)=g(x)+h(x)
(g – low degree, h – sparse, low weight deg)
•
Case 1: wt-deg(g)>wt-deg(h): (less interesting case)
–
Eliminate h
by derivatives
–
Use
Weil theorem
for derivatives of g
•
Case 2: wt-deg(g)<wt-deg(h):
–
Eliminate g
by derivatives
–
Convert h to
multi-linear
–
Use sparsity of h to “shift” it and make it have
low-degree
–
Analyze using
minimal distance
of low-degree polynomials
•
Case 3: wt-deg(g)=wt-deg(h)
–
Similar to 2, but only
partially eliminate g
Summary and
open problems
@+a+
+%=!?
Summary
•
Weil bound: estimates for character sums
evaluated on low-degree polynomials
•
Main limitation: degree bound
•
We give a new extension, allowing a few
monomials to have
high degree
(but
low weight
degree
)
•
Application to testing affine invariant codes
Open problems 1: Weil bound
•
Extend the Weil bound to interesting families
of polynomials of degree
•
Applications
–
Number theory
–
Cryptography
–
Coding
–
Explicit constructions
–
?
Open problems 2: Succinctness
•
P vs NP is really a question about
succinctness
•
Sparse polynomials: succinct algebraic circuits
•
Bourgain, this work,…: character sum estimates
for
sparse polynomials
which are
not true for
non-sparse polynomials
•
L.-Srinivasan: correlation bounds for sparse polys
•
Extend to less sparse polynomials, more general
algebraic circuits, boolean circuits, …
Thank you
Tali Kaufman and Shachar Lovett present a new extension of the Weil bound for character sums, providing applications to coding theory. The Weil bound offers insights into the behavior of low-degree polynomials, distinguishing between structured and random-like functions. This extension has implications for number theory, analysis, algebra, explicit constructions, derandomization, lower bounds, and coding theory. The talk discusses additive characters in finite fields and explores the properties of polynomials over such characters, touching upon cases of uniform distribution and constants. Generalizations to multi-variate polynomials are also highlighted, along with advancements in handling sparse polynomials beyond the root field size.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
New extension of the Weil bound for character sums, and applications to coding Tali Kaufman (Bar-Ilan) Shachar Lovett (IAS) FOCS, October 2011
Talk overview Weil bound for character sums Our new extension for the Weil bound Application: testing of affine invariant codes Proof overview Open problems
Character sums @+a+ +%=?
Weil bound for character sums Formal way of saying: Low-degree polynomials are either: - very structured; or - behave like random functions Extremely useful tool in Number theory, analysis, algebra, Explicit constructions, derandomization, lower bounds, coding theory,
Additive characters finite field Additive character: map F such that ( ) ( ) a b * : F a b + = ( ) Example: prime field ( ) c a = = F F p = F 2 / ca i p ( , ) e c p p p Example: non-prime field 2n F F ( ) ( c a = = F , a c n 1 ) ( ) c 2
Weil bound for character sums f(x) - degree d polynomial over additive character : F F Then either (1) is constant for all or (2) is uniformly distributed ( ( )) f a 1 ( ( )) a F F a F ( ( )) f a F 1 d f a | |
Weil bound: examples = = 2 Example 1: squares are uniform in F F , ( ) pf x x F p = = + Example 2: f(x) lies in a subspace of co-dim 1 c 0, ( ( )) 2 F F , ( ) n f x x x 2 cf x = ( 1) = ( ), f x c 1
Weil bound for character sums f(x) degree d polynomial is constant; or ( ( )) f F 1 F 1 d ( ( )) f a | | F a Many generalizations: Multi-variate polynomials (Deligne), polynomials on curves (Bombieri), Main limitation: useful only when | F | d
Going beyond root field size We can go beyond degree if we restrict ourselves to sparse polynomials | F | Bourgain: Let f(x) be a sparse polynomial of degree . Then either is constant or ( ( )) f 1 ( ( )) a F F 1 | | F 1 f a
Going beyond root field size = We consider polynomials over (or ) Degree of xe is e Weight degree of xe is the hamming weight of e (equiv: degree as n-variate polynomial over ) F F= F 2n n p 2 F We show: Let f(x) be a sparse polynomial of low weight degree. Then either is constant or ( ( )) f 1 ( ( )) a F F 1 f a
Going beyond root field size = Consider polynomials over (or ) Degree of xe is e Weight degree of xe is the hamming weight of e (equiv: degree as polynomial over ) F F= F = F F 2n n p 2n Bourgain: sparsity ~log(n) This work: sparsity n0.1 (assumes d=O(log n)) n F 2 We show: Let f(x) be a sparse polynomial of low weight degree. Then either is constant or ( ( )) f 1 ( ( )) a F F 1 f a
Good subcodes of Reed-Muller Reed-Muller code: multivariate polynomials in of degree d 2 1 [ , , ] n x x F Equivalently: univariate polynomials in of weight degree d F 2[ ] n x We show: For d=O(log n), sub-code of sparse polynomials with n0.1 monomials forms a (non- linear) code with near optimal distance
Going beyond root field size We can actually show a stronger result, combining Weil bound with sparse polynomials Let f(x)=g(x)+h(x) where g(x) has degree h(x) is sparse, low weight degree Then either is constant or ( ( )) f 1/2 | | F 1 F ( ( )) f a 1 F a
Character sums in coding theory @+a+ +%=!
Locally testable codes Codes where codewords can (whp) be verified to be (nearly) correct with only a few queries Combinatorial heart of many PCP constructions Big question: can locally testable codes form good codes (constant rate & distance)
Locally testable codes Constructions: Hadamard [BLR] Polynomials [Alon-Kaufman-Krivelevich-Litsyn- Ron, Arora-Sudan, Samorodnitsky, Raz-Safra, Moshkovitz-Raz, ] Combinatorial [Dinur-Goldenberg, Imagliazzo- Kabanets-Wigderson, ]
Locally testable codes General families of codes which guarantee local testability: Near orthogonal codes [Kaufman-Litsyn] Random sparse codes [Kaufman-Sudan, Kopparty- Saraf] Sparse affine invariant codes [Grigorescu-Kaufman- Sudan] We show: slightly less sparse affine invariant codes are still locally testable
Affine invariant codes : F F f Codeword: function 2 n 2 Code: linear subspace C { : F F } f 2 n 2 Code is affine invariant if it is invariant under affine transformations of the input, i.e. ( ) ( ) g x f x = C x b + ( ) C f a
Testing of affine invariant codes Grigorescu-Kaufman-Sudan: Any affine invariant code with exp(n) codewords (i.e. sparse) can be locally testable with O(1) queries C { : F F } f 2 n 2 Use Bourgain character sum estimate for sparse polynomials
Testing of affine invariant codes This work: Any affine invariant code with exp(n1+ ) codewords (slightly less sparse) can be locally testable with poly(n ) queries C { : F F } f 2 n 2 Use the fact that our character sum estimate works for slightly less sparse polynomials
Proof overview @+a+ +%=!!
Main theorem = f(x)=g(x)+h(x) polynomial over g(x) has degree h(x) sparse polynomial of low weight degree F F= n p | F | Then either is constant or ( ( )) f F E [ ( ( ) f x ) 1 x
Main proof ideas Use derivatives + convexity to reduce degrees and wt deg f(x)=g(x)+h(x) (g low degree, h sparse, low weight deg) Case 1: wt-deg(g)>wt-deg(h): (less interesting case) Eliminate h by derivatives Use Weil theorem for derivatives of g Case 2: wt-deg(g)<wt-deg(h): Eliminate g by derivatives Convert h to multi-linear Use sparsity of h to shift it and make it have low-degree Analyze using minimal distance of low-degree polynomials Case 3: wt-deg(g)=wt-deg(h) Similar to 2, but only partially eliminate g
Summary and open problems @+a+ +%=!?
Summary Weil bound: estimates for character sums evaluated on low-degree polynomials Main limitation: degree bound | F | d We give a new extension, allowing a few monomials to have high degree (but low weight degree) Application to testing affine invariant codes
Open problems 1: Weil bound Extend the Weil bound to interesting families of polynomials of degree | F | Applications Number theory Cryptography Coding Explicit constructions ?
Open problems 2: Succinctness P vs NP is really a question about succinctness Sparse polynomials: succinct algebraic circuits Bourgain, this work, : character sum estimates for sparse polynomials which are not true for non-sparse polynomials L.-Srinivasan: correlation bounds for sparse polys Extend to less sparse polynomials, more general algebraic circuits, boolean circuits,
