Question sur le papier `` Auto-test / correction des polynômes et pour des fonctions approximatives ''

Question

J'ai du mal à vraiment comprendre une compréhension précise de certains des Auto-test / correction des polynômes et pour les fonctions approximatives et apprécierait grandement l'aide. Voici ma compréhension de la section 3, Polynômes d'auto-test.

Mon principal problème est que la définition de la fonction $ g $ semble nécessiter un théorème qui n'est pas cité. Détails ci-dessous.

---

L'un reçoit un programme $ P $. Ce programme calcule (soi-disant) une fonction polynomiale $ f $. Ce polynôme $ f $ est défini implicitement en disant que $ f $ est le polynôme interpolant, sur un champ fini $ F $, des points de données $ (x_0, y_0) $, $ (x_1, y_1) $, $ DOTS $, $ (x_n, y_d) $. Autrement dit, $ f $ Le polynôme le plus bas est-il satisfaisant pour tous $ i = 0,1, points, d $, $ f (x_i) = y_i $. Dans tous les cas, $ P $ devrait être très rapide à calculer, le meilleur scénario étant certainement où $ P $ est une liste (soi-disant) toutes les valeurs de $ f $ Pré-rémunéré.

On veut un moyen rapide de vérifier cela $ P $ fait son travail comme annoncé, du moins principalement.

Pendant la preuve que le programme Auto-test polynomial a les propriétés souhaitées, on introduit la fonction $ g $ défini comme$$ 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) droite } $$où le $ alpha_i $ sont les éléments de terrain qui satisfont, pour tout polynôme $ Q $ degré de degré $ leq d $, $$ q (x) = sum_ {i = 1} ^ {d + 1} alpha_i q (x + i cdot t) $$Ceux-ci existent et peuvent être définis en termes d'inverse d'une matrice Vanderonde, et le papier nous dit même qu'ils sont des coefficients binomiaux jusqu'à un signe.

Le but est bien résumé par les auteurs: prouver que dans certaines circonstances, la fonction $ g $ Ainsi `` défini '' est en effet le polynôme interpolant des données, et est surtout d'accord avec $ P $:

Il n'est pas clair pour moi comment interpréter la définition de $ g $. Il y a deux définitions que l'on pourrait trouver:

1) $ g (x) $ est la valeur qui vient le plus souvent de tous les $ sum_ {i = 1} ^ {d + 1} alpha_i p (x + i cdot t) $, mais cela nous obligerait à rompre les liens (probablement arbitrairement). C'est inacceptable Considérant un lemme plus bas, qui nous dit que dans certaines conditions $ g $ est précisément la fonction $ f $ recherché

2) Si nous considérons la totalité des valeurs $ sum_ {i = 1} ^ {d + 1} alpha_i p (x + i cdot t) $, pour tous $ t in f $, là toujours est un 50 $ % + epsilon $ majorité d'une valeur. Dans ce cas, la définition est sans ambiguïté, mais qui aurait besoin d'une preuve, disant probablement que si $ delta $ est assez petit (et j'espère que `` assez petit '' peut entièrement de défini en termes de $ d $ et $ delta $, c'est-à-dire n'utilisant pas la cardinalité $ | F | $ du champ fini $ F $)

2 ') ou nous pourrions partir $ g $ non défini dans les cas où non 50 $ % + epsilon $ La majorité survient, mais cela rendrait sûrement l'analyse plus compliquée.

Il semble que le second ait du sens, et lorsque l'on considère une preuve qui vient par la suite, il semble que ce soit en effet la définition qu'ils utilisent. Cependant, il faudrait la preuve qu'avec $ delta $ Assez petit, un 50 $ % + epsilon $ arrive toujours.

Ici $ $ Delta $ est défini comme (je crois qu'il y a une faute de frappe dans le journal ici):

Lorsque vous effectuez une analyse similaire avec $ F_2 $-Partes linéaires $ F à f_2 $ pour un champ de caractéristique $2$, il y a un résultat très mignon de la théorie de la représentation qui nous dit que si $ f $ satisfait l'équation déterminante d'une carte linéaire ``$ f (x + y) = f (x) + f (y) $'' Assez souvent, alors il est d'accord avec une carte linéaire réelle au moins aussi souvent (en termes de distance de Hamming). Il semble que les auteurs visent un résultat similaire ici, mais il manque un morceau pour autant que je sache.