Esercizio - Schwartz-Zippel su identità vere e false modulo 101

Testo. Si lavora nel campo $\mathbb F_{101}$ (interi modulo $101$) con $S=\mathbb F_{101}$. Si vuole verificare, valutando in un punto casuale, le identità

• (I) $(x+y)^3=x^3+3x^2y+3xy^2+y^3$;
• (II) $(x+y)^3=x^3+y^3$;
• (III) $(x+y)^2=x^2+y^2$.

1. Valutare (I) e (II) nel punto $(37,58)$.
2. Per (II) e (III) scrivere il polinomio differenza, il suo grado, il bound di Schwartz-Zippel e il numero esatto di punti di $\mathbb F_{101}^2$ in cui si annulla.
3. Quante prove indipendenti servono per smascherare (II) con errore $\le10^{-6}$ usando il bound? Quante servirebbero con la probabilità esatta?
4. Per il polinomio $P=\prod_{i=1}^5(x_i-i)$ in $5$ variabili, con $S=\mathbb F_{101}$, calcolare la probabilità esatta di annullamento e confrontarla con il bound.

Teoria: Union bound e verifica randomizzata - identità polinomiali e prodotti di matriciSpazi discreti richiamati; inclusione-esclusione (con le troncate di Bonferroni) e union bound Pr[unione] ≤ somma, valido senza indipendenza e stretto quando gli eventi sono rari (collisioni: C(n,2)/m). Principio delle decisioni differite: si fissa tutto tranne una scelta casuale e si limita la probabilità su quella. Lemma di Schwartz-Zippel: un polinomio non nullo di grado totale d, valutato in un punto di S^n scelto uniformemente, si annulla con prob ≤ d/|S| (induzione sul numero di variabili); test di identità polinomiale con errore unilaterale, ripetuto (d/|S|)^k. Freivalds: per verificare AB=C si controlla A(Br)=Cr con r in {0,1}^n in tempo O(n^2), errore ≤ 1/2 (stretto), 2^-k con k prove. Fingerprint: due stringhe di n bit si confrontano con a mod p per un primo casuale p ≤ M, errore ≤ n/π(M).Union bound e verifica randomizzata - identità polinomiali e prodotti di matrici → (sezione 3); CampiUn campo è un insieme di numeri con somma e prodotto che rispettano le regole usuali (associativa, commutativa, neutri, opposti, inversi, distributiva): è ciò che serve per risolvere le equazioni di primo grado. Esempi: Q, R, C e i campi finiti.Campi →.

Soluzione

Punto 1. $(37,58)$: $x+y=95$ e $95^3=857375=8488\cdot101+87\equiv87$.

• (I): lato destro $37^3+3\cdot37^2\cdot58+3\cdot37\cdot58^2+58^3\equiv87$. Coincidono (è vero per ogni punto: la differenza è il polinomio nullo).
• (II): $x^3+y^3\equiv32\ne87$. La differenza $87-32=55\ne0$: l'identità (II) è dichiarata falsa, con certezza (un valore diverso prova che i polinomi sono diversi).

Punto 2.

• (II): differenza $D=(x+y)^3-x^3-y^3=3x^2y+3xy^2=3xy(x+y)$, grado totale $d=3$, non nulla. Bound: $d/|S|=3/101=0{,}0297$. $D(x,y)=0$ se e solo se $x=0$ oppure $y=0$ oppure $x+y\equiv0$ (si usa che in un campo un prodotto è nullo solo se lo è un fattore). Le tre «rette» hanno $101$ punti ciascuna e si incontrano a coppie solo in $(0,0)$: per inclusione-esclusione $3\cdot101-3\cdot1+1=301$ punti. Probabilità esatta $301/10201=0{,}0295$, quasi uguale al bound: Schwartz-Zippel è quasi stretto.
• (III): $D=2xy$, grado $2$, bound $2/101=0{,}0198$. Zeri: $x=0$ o $y=0$: $101+101-1=201$ punti, probabilità $201/10201=0{,}0197$ (ancora quasi stretto).

Punto 3. Con $k$ prove indipendenti l'errore (l'identità falsa sembra vera in tutte) è $\le(3/101)^k$. Serve $(3/101)^k\le10^{-6}$: $k\ge\frac{\ln10^{6}}{\ln(101/3)}=\frac{13{,}8155}{3{,}5165}=3{,}93$, quindi $k=4$. Con la probabilità esatta $0{,}0295$ servono $\frac{13{,}8155}{3{,}5231}=3{,}92$, anch'essi $k=4$.

Punto 4. $P=0$ se almeno un fattore si annulla, cioè se $x_i=i$ per qualche $i$. Le $x_i$ sono indipendenti e $\Pr[x_i=i]=1/101$, quindi $$\Pr[P=0]=1-\Big(1-\frac1{101}\Big)^5=1-0{,}95147=0{,}04853 .$$ Il bound è $d/|S|=5/101=0{,}04950$: l'unione dei $5$ eventi è quasi disgiunta, il bound (che qui coincide con l'union bound) è molto vicino.

Risultati: (II) è smascherata in $(37,58)$; zeri esatti $301/10201$ per (II) e $201/10201$ per (III); $k=4$ prove; $0{,}04853$ contro $0{,}04950$.

p = 101
print(pow(95, 3, p), (37**3 + 3 * 37**2 * 58 + 3 * 37 * 58**2 + 58**3) % p, (37**3 + 58**3) % p)
z2 = sum((3 * x * y * (x + y)) % p == 0 for x in range(p) for y in range(p))
z3 = sum((2 * x * y) % p == 0 for x in range(p) for y in range(p))
print(z2, z3, z2 / p**2, 3 / p, z3 / p**2, 2 / p)
print(1 - (1 - 1 / p)**5, 5 / p)