New Extension of the Weil Bound for Character Sums
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,
