Domanda sul documento `` autotest/correzione per i polinomi e per funzioni approssimative ''

Question

Ho qualche problema a capire davvero una comprensione di alcuni di Autotest/correzione per polinomi e per funzioni approssimative e apprezzerei molto l'aiuto. Ecco la mia comprensione della sezione 3, Polinomi auto-test.

Il mio problema principale è che la definizione della funzione $ g $ Sembra richiedere un teorema che non è citato. Dettagli di seguito.

---

Uno viene dato un programma $ P $. Questo programma (presumibilmente) calcola una funzione polinomiale $ f $. Questo polinomio $ f $ è definito implicitamente dicendo questo $ f $ è il polinomio interpolante, su un campo finito $ F $, di punti dati $ (x_0, y_0) $, $ (x_1, y_1) $, $ dots $, $ (x_n, y_d) $. In altre parole, $ f $ è il polinomio più basso soddisfacente per tutti $ i = 0,1, dots, d $, $ f (x_i) = y_i $. In ogni caso, $ P $ Dovrebbe essere molto veloce da calcolare, lo scenario migliore è sicuramente dove $ P $ è un elenco di (presumibilmente) tutti i valori di $ f $ pre-computato.

Uno vuole un modo rapido per verificarlo $ P $ Fa il suo lavoro come pubblicizzato, almeno principalmente.

Durante la prova che il programma Autotest polinomiale ha le proprietà desiderate, si introduce la funzione $ g $ definito come$$ forall x in f, quad g (x) = mathrm {maj} _ {t in f} left { sum_ {i = 1}^{d+1} alpha_i p (x +i CDOT T) Right } $$dove il $ alpha_i $ sono gli elementi sul campo che soddisfano, per qualsiasi polinomio $ Q $ di laurea $ leq d $, $$ q (x) = sum_ {i = 1}^{d+1} alpha_i q (x+i CDot t) $$Questi esistono e possono essere definiti in termini di inverso di una matrice Vandermonde e la carta ci dice persino che sono coefficienti binomiali fino a un segno.

L'obiettivo è ben riassunto dagli autori: dimostrare che in determinate circostanze, la funzione $ g $ Così `` definito '' è davvero il polinomio interpolante dei dati e concorda principalmente con $ P $:

Non mi è chiaro come interpretare la definizione di $ g $. Ci sono due definizioni che si potrebbero inventare:

1) $ g (x) $ è il valore che emerge più spesso da tutti i $ sum_ {i = 1}^{d+1} alpha_i p (x+i CDot t) $, ma questo ci richiederebbe di rompere i legami (probabilmente arbitrariamente). Questo è inaccettabile Considerando un lemma più in basso che ci dice che in determinate condizioni $ g $ è precisamente la funzione $ f $ ricercato

2) Se consideriamo la totalità dei valori $ sum_ {i = 1}^{d+1} alpha_i p (x+i CDot t) $, per tutti $ t in f $, là sempre è un $ 50 %+ epsilon $ maggioranza di un valore. Nel qual caso la definizione è inequivocabile, ma quale richiederebbe una prova, probabilmente dirlo se se $ Delta $ è abbastanza piccolo (e si spera `` abbastanza piccolo '' può essere completamente definito in termini di $ d $ e $ Delta $, cioè non usare la cardinalità $ | F | $ del campo finito $ F $)

2 ') o potremmo andarcene $ g $ non definito in quei casi in cui no $ 50 %+ epsilon $ La maggioranza sorge, ma ciò renderebbe sicuramente l'analisi più complicata.

Sembra che solo il secondo abbia senso, e quando si considera una prova che viene dopo, sembra che questa sia davvero la definizione che stanno usando. Tuttavia, richiederebbe la prova che con $ Delta $ abbastanza piccolo, a $ 50 %+ epsilon $ succede sempre.

Qui $ 1- Delta $ è definito come (credo che ci sia un errore di battitura nel documento qui):

Quando fai un'analisi simile con $ F_2 $-Nelear mappe $ F a f_2 $ per un campo di caratteristica $2$, c'è un risultato molto carino dalla teoria della rappresentazione che ci dice che se $ f $ soddisfa l'equazione di definizione di una mappa lineare ``$ f (x+y) = f (x)+f (y) $'' Spesso, quindi è d'accordo con una mappa lineare effettiva almeno altrettanto spesso (in termini di distanza di martellare). Sembra che gli autori stiano puntando a un risultato simile qui, ma manca un pezzo per quanto posso dire.