Some Pseudorandom Phenomena in Finite Fields

on YouTube ↗44m

" summary

Proves two concrete independence results: multiplicative characters like the cubic residue character have negligible correlation with Boolean polynomials of degree up to about n^{0.1}, via a reduction to depth‑bounded arithmetic circuits and a Razborov‑Smolensky style argument that shows such circuits (size ≲2^{n^{O(1)/D}}) cannot beat 1/3 by more than n^{-0.1}; a random self-reduction amplifies this to the stated correlation bound. Separately shows trace(x^7) is nearly balanced on any subspace of dimension ~0.4n that is not contained in a proper subfield, using additive image/kernel polynomials QA and a combinatorial lemma ruling out long runs of zero coefficients.

AI-written summary · about

" chapters (8)

1. 0:00Introduction to pseudo-randomness
2. 2:57Correlation theorems
3. 7:14Subspace constraints
4. 11:19Proof approach via circuits
5. 17:13Random self-reduction
6. 24:35Versatility of functions
7. 31:43Additive combinatorial lemma
8. 35:08Subspace analysis and conclusion