Adversarial Wronskians: A proof of the Kung--Traub conjecture

Matthew J. Colbrook

Résumé IA · arXiv: 2610.40660v1 · math.NA

Adversarial Wronskians: A proof of the Kung--Traub conjecture

Matthew J. Colbrook

Article original Soumis à arXiv le 20 Sep. 2026 Formal verification: https://github.com/MColbrook/Kung-Traub_conjecture Licence : NONEXCLUSIVE-DISTRIB 1.0 Aussi en : en

Comment lire ce résumé ? Guide illustré

L’essentiel

L’article prouve que l’ordre local universel d’une méthode déterministe sans mémoire utilisant au plus n évaluations scalaires est borné par 2^(n−1), borne atteinte pour n ≥ 2.

Question

Quelle est la meilleure convergence locale qu’une méthode déterministe stationnaire sans mémoire peut garantir pour toute fonction analytique ayant un zéro simple, avec au plus n évaluations de la fonction ou de ses dérivées par itération ? La borne dépend-elle de l’organisation des évaluations en groupes ?

Méthode

L’auteur établit une borne inférieure à échelle fixée en construisant des familles de perturbations polynomiales de degré au plus n qui donnent les mêmes observations, et utilise la localisation des zéros des Wronskiens pour contrôler la séparation des racines. Une construction diagonale de corrections analytiques produit ensuite une fonction entière unique pour laquelle l’estimation d’ordre supérieur échoue le long d’une suite de départs ; les fonctions obtenues vérifient 3/4 ≤ f′(t) ≤ 5/4 sur la droite réelle. Le travail donne aussi une borne pour des évaluations en groupes, ℓ₁∏ⱼ₌₂ᵏ(ℓⱼ+1), traite les évaluations complexes et annonce une vérification formelle dans Lean.

Résultats

Résultat Pour n évaluations scalaires réelles, aucune méthode déterministe stationnaire sans mémoire ne garantit un ordre local universel supérieur à 2^(n−1).
Résultat Pour n ≥ 2, les méthodes de Kung et Traub atteignent la borne d’ordre 2^(n−1).
Résultat Lorsque les observations sont réparties en k groupes prédéfinis de tailles ℓ₁,…,ℓₖ, l’ordre universel est au plus ℓ₁∏ⱼ₌₂ᵏ(ℓⱼ+1).
Voir le passage dans l’article
Then its universal local order is at most $$\ell_{1}\prod_{j=2}^{k}(\ell_{j}+1).$$
Résultat La borne analogue vaut pour les évaluations scalaires complexes, au sens où une fonction entière et une suite de départs peuvent faire échouer tout ordre p supérieur à 2^(n−1).
Interprétation des auteurs L’obstruction ne dépend pas d’un mauvais conditionnement du zéro réel : la fonction entière contre-exemple peut avoir une dérivée uniformément proche de un sur la droite réelle.
Voir le passage dans l’article
The counterexample can be chosen entire and strictly increasing, with derivative uniformly close to one.

Limites

Le résultat porte sur des méthodes déterministes stationnaires sans mémoire et ne fournit pas ici une borne générale pour les méthodes avec mémoire.
Voir le passage dans l’article
In particular, there is no information retained from earlier iterations other than the current starting point.
La borne d’atteignabilité par les méthodes de Kung et Traub est établie dans l’article pour n ≥ 2 ; le cas n = 1 n’est pas inclus dans cette affirmation de netteté.

Portée

Le travail établit la borne supérieure conjecturée par Kung et Traub en autorisant des choix adaptatifs arbitraires de points et d’ordres de dérivation, ainsi qu’un traitement des données sans restrictions de régularité. Il complète la borne par des résultats pour les évaluations groupées et complexes, et fournit selon les auteurs une vérification formelle des résultats dans Lean.

Rédigé par une IA à partir de l’article. Les passages cités sont vérifiés mot pour mot dans le texte analysé ; le reste peut contenir des erreurs.

Mots clés générés par l'IA : recherche de racines méthodes sans mémoire convergence locale borne d’ordre vérification formelle

Pour aller plus loin

Résumé Complet
Résumé vulgarisé
Article de blog
Abstract original

L’article établit une borne fondamentale pour les méthodes déterministes de recherche de racines sans mémoire. Il étudie les algorithmes qui, à chaque itération, partent d’un point courant, effectuent au plus $n$ observations scalaires d’une fonction réelle analytique ou de ses dérivées, puis produisent une approximation de la racine. Les points d’évaluation et les ordres de dérivation peuvent être choisis de manière adaptative, sans autre restriction. La question est de déterminer l’ordre local de convergence qu’une telle méthode peut garantir pour toute fonction ayant une racine simple. Le résultat central montre qu’aucun algorithme de cette classe ne peut garantir, pour toutes les fonctions admissibles, un ordre local supérieur à $2^n-1$. Plus précisément, pour tout exposant $p>2^n-1$, l’article construit une fonction entière, réelle sur l’axe réel, ainsi qu’une suite de points de départ convergeant vers son unique racine, pour laquelle l’erreur de l’algorithme ne décroît pas aussi rapidement qu’une puissance $p$ de l’erreur initiale. La fonction construite est même bien conditionnée : sa dérivée reste comprise entre $3/4$ et $5/4$ sur toute la droite réelle. La difficulté ne s’explique donc ni par une racine multiple ni par un mauvais comportement local de la fonction. La preuve combine une borne valable à échelle fixe et une construction diagonale qui produit une seule fonction invalidant l’ordre de convergence annoncé. À chaque échelle, les auteurs considèrent une famille de perturbations paramétrée par les coefficients d’un polynôme de degré au plus $n$. Chaque observation impose au plus une contrainte linéaire sur ces paramètres. Toutefois, le simple décompte des contraintes ne suffit pas : il faut également montrer qu’après les observations, des racines suffisamment éloignées restent possibles. Pour ce faire, l’article établit un lemme de localisation des zéros des wronskiens de sous-espaces polynomiaux. Ce lemme décrit le lien entre les racines d’un polynôme appartenant au noyau des observations et les points interdits par l’algorithme. En choisissant les réponses successivement, les auteurs préservent un ensemble de fonctions qui produisent exactement le même transcript, tout en ayant des racines différentes. Puisque l’algorithme reçoit les mêmes données, il renvoie la même valeur pour ces fonctions et se trompe donc nécessairement sur au moins l’une d’elles. Après $n$ observations, la séparation entre les racines est d’au moins une constante multipliée par l’échelle initiale élevée à la puissance $2^n-1$. Les auteurs construisent ensuite des corrections analytiques successives qui préservent exactement toutes les observations antérieures et dont la somme converge. La limite obtenue est une fonction entière qui conserve les mauvaises performances de l’algorithme le long d’une suite de points de départ. Cette étape est essentielle : des contre-exemples distincts à chaque échelle ne suffiraient pas, car la constante de convergence peut dépendre de la fonction. Pour $n\geq 2$, la borne est optimale : les méthodes multipoints de Kung et Traub atteignent l’ordre $2^n-1$. L’article examine également les évaluations organisées en groupes. Pour des groupes de tailles $\ell_1,\ldots,\ell_k$, l’ordre universel est au plus $\ell_1\prod_{j=2}^{k}(\ell_j+1)$.

Adversarial Wronskians : une borne fondamentale pour la recherche de racines

Comment savoir si une méthode numérique peut être rendue plus rapide simplement en choisissant plus habilement ses observations ? Dans « Adversarial Wronskians: A proof of the Kung--Traub conjecture », Matthew J. Colbrook étudie cette question pour les algorithmes déterministes de recherche de racines sans mémoire. Son résultat central fixe une limite précise : avec au plus n observations scalaires par itération, aucune méthode de cette classe ne peut garantir un ordre local de convergence supérieur à 2n − 1 pour toutes les fonctions admissibles.

Une question sur la vitesse de convergence

Une méthode de recherche de racines produit, à chaque itération, une nouvelle approximation à partir d’observations de la fonction et, éventuellement, de ses dérivées. Dans le cadre étudié, elle peut choisir de façon adaptative les points où elle observe la fonction ainsi que les ordres de dérivation. La seule limite est le nombre d’observations scalaires : au plus n à chaque étape.

L’ordre local de convergence décrit la rapidité avec laquelle l’erreur diminue à mesure que l’approximation se rapproche d’une racine. Un ordre élevé signifie une réduction particulièrement rapide de l’erreur. La question est donc ambitieuse : avec une quantité limitée d’informations par itération, quel ordre de convergence peut-on garantir, quelle que soit la fonction rencontrée ?

La borne : 2n − 1

Colbrook montre qu’il existe une limite fondamentale. Pour tout exposant p supérieur à 2n − 1, on peut construire une fonction entière, réelle sur l’axe réel, et une suite de points de départ qui convergent vers son unique racine, mais pour lesquelles l’algorithme ne réduit pas l’erreur aussi vite qu’une puissance p de l’erreur initiale.

Le contre-exemple est d’autant plus frappant que la fonction reste bien conditionnée : sa dérivée est comprise entre 3/4 et 5/4 sur toute la droite réelle. L’échec ne s’explique donc ni par une racine multiple ni par une fonction au comportement irrégulier près de sa racine. Il révèle plutôt une limite liée à la quantité d’information disponible pour l’algorithme.

Comment construire un contre-exemple qui dure

La preuve doit relever deux défis. Il ne suffit pas de montrer qu’à une échelle donnée certaines observations laissent plusieurs racines possibles. Il faut aussi construire une seule fonction qui déjoue l’algorithme le long d’une suite de points de départ. Sans cela, les mauvais exemples pourraient changer d’une échelle à l’autre, et la constante de convergence pourrait dépendre de la fonction.

Des observations qui laissent des possibilités ouvertes

À chaque échelle, les auteurs étudient une famille de perturbations décrites par les coefficients d’un polynôme de degré au plus n. Chaque observation apporte au plus une contrainte linéaire sur ces paramètres. Mais compter les contraintes ne suffit pas : il faut également garantir que certaines racines restent assez éloignées pour mettre en défaut la sortie de l’algorithme.

C’est là qu’intervient un lemme de localisation des zéros des wronskiens de sous-espaces polynomiaux. Il relie les racines des polynômes qui échappent aux contraintes d’observation aux points que l’algorithme ne peut pas utiliser. En choisissant les réponses au fil des observations, les auteurs préservent plusieurs fonctions produisant exactement les mêmes données, ou « transcript », tout en ayant des racines différentes.

L’algorithme reçoit donc les mêmes informations pour ces fonctions et renvoie nécessairement la même approximation. Cette réponse ne peut être correcte pour toutes les racines possibles. Après n observations, la séparation entre certaines racines demeure au moins égale à une constante multipliée par l’échelle initiale élevée à la puissance 2n − 1.

Des corrections successives et une fonction unique

Pour transformer cet argument à une échelle en un véritable contre-exemple, l’article construit des corrections analytiques successives. Chacune préserve exactement toutes les observations antérieures, et leur somme converge. La fonction limite est entière et conserve les mauvaises performances de l’algorithme le long d’une suite de points de départ convergeant vers sa racine.

Cette construction diagonale est essentielle : elle rassemble les difficultés rencontrées à différentes échelles dans une même fonction, au lieu de s’appuyer sur une succession de contre-exemples distincts.

Une borne optimale et des observations par groupes

Pour n supérieur ou égal à 2, la borne est optimale : les méthodes multipoints de Kung et Traub atteignent l’ordre 2n − 1. Le résultat établit ainsi une correspondance nette entre la limite théorique et les performances réalisables.

L’article examine aussi les méthodes où les évaluations sont organisées en groupes. Pour des groupes de tailles ℓ1, …, ℓk, l’ordre universel ne peut dépasser ℓ1 multiplié par le produit des termes ℓj + 1 pour les groupes suivants. Cette formule précise comment la structure des observations influe sur la vitesse de convergence garantie.

Pourquoi ce résultat compte

« Adversarial Wronskians » montre que l’adaptativité ne supprime pas les limites de l’information disponible. Même une méthode déterministe autorisée à choisir ses points et ses dérivées peut être mise en difficulté par une fonction soigneusement construite, mais pourtant régulière et bien conditionnée. La preuve ne se contente pas d’un argument de comptage : elle combine géométrie des zéros, indistinguabilité des observations et construction analytique pour établir une borne universelle, puis démontrer qu’elle est optimale dans le cadre considéré.

Créé le 02 Nov. 2026

Cette synthèse vous a-t-elle été utile ?

Note : 0

Posez des questions sur cet article à notre assistant IA

Comment discuter avec cet article ? Guide illustré

Comparer avec le PDF

Vous pouvez aussi discutez avec plusieurs papiers à la fois ici.

Instructions pour utiliser l'assistant IA ?

Outils pour cet article

Expliquer autrement 3 réécritures gratuites restantes aujourd'hui

Enregistrer dans une collection Regroupez des articles en collections pour les comparer, les interroger et les exporter. Créer un compte gratuit Se connecter

Exporter BibTeX · RIS (Zotero, Mendeley, EndNote) · Obsidian (Markdown) · Notion (Markdown)

Outils avancés Premium

Pour suivre un domaine de près : alertes de citations, diapositives de journal club, comparaison des versions et envoi vers Zotero. Découvrir Premium

Zotero

Alertes de citation Guide des alertes de citations

Qui travaille dessus ? Les personnes et institutions qui publient sur son sujet

Lettre hebdomadaire Présenté dans « Mathématiques et statistiques cette semaine » du 2 novembre 2026. Mathématiques et statistiques cette semaine : les conjectures à l’épreuve des preuves

Journal club Premium+ Des slides pour le présenter Proposer pour le journal club

Versions Ce qui a changé entre les versions

En parler en public Premium+ Kit presse : communiqué, questions, détecteur de hype Guide du kit presse

Les articles autour de celui-ci

Les voir sur une carte

Classés selon la proximité de leur titre et de leur résumé avec ceux de cet article. Sélectionnez-en pour les lire ensemble.

Les articles les plus proches

Apparenté Contexte plus large
An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
Matthew Kwan, Lisa Sauermann · 2019 · Combinatorics · cité 7 fois · Résumé IA disponible

« An algebraic inverse theorem » étudie la concentration de polynômes quadratiques de variables de Bernoulli, sans traiter la convergence des méthodes de recherche de zéros.

Résumé scientifique
Consider a quadratic polynomial $f\left(\xi_{1},\dots,\xi_{n}\right)$ of independent Bernoulli random variables. What can be said about the concentration of $f$ on any single value? This generalises the classical Littlewood--Offord problem, which asks the same question for linear polynomials. As in the linear case, it is known that the point probabilities of $f$ can be as large as about $1/\sqrt{n}$, but still poorly understood is the "inverse" question of characterising the algebraic and arithmetic features $f$ must have if it has point probabilities comparable to this bound. In this paper we prove some results of an algebraic flavour, showing that if $f$ has point probabilities much larger…
Apparenté Contexte plus large
Certified homotopy tracking using the Krawczyk method
Timothy Duff, Kisun Lee · 2024 · Numerical Analysis · cité 14 fois · Résumé IA disponible

« Certified homotopy tracking » certifie des trajectoires de solutions de systèmes polynomiaux, tandis que l’article étudie l’ordre des méthodes de recherche de zéros.

Résumé scientifique
We revisit the problem of certifying the correctness of approximate solution paths computed by numerical homotopy continuation methods. We propose a conceptually simple approach based on a parametric variant of the Krawczyk method from interval arithmetic. Unlike most previous methods for certified path-tracking, our approach is applicable in the general setting of parameter homotopies commonly used to solve polynomial systems of equations. We also describe a novel preconditioning strategy and give theoretical correctness and termination results. Experiments using a preliminary implementation of the method indicate that our approach is competitive with specialized methods appearing previousl…
Apparenté Contexte plus large
Weak Poincaré Inequalities via Approximate Stochastic Localization: Application to Sampling the Sherrington-Kirkpatrick Model
Ewan Davies, Holden Lee, Juspreet Singh Sandhu et al. · 2026 · Probability · cité 3 fois · Résumé IA disponible

« Weak Poincaré Inequalities » établit une inégalité fonctionnelle pour le modèle de Sherrington-Kirkpatrick, sans étudier les méthodes de recherche de zéros.

Résumé scientifique
We develop a new method for proving a weak functional inequality by first proving it for a sufficiently regular sequence of distributions approximating the stochastic localization (SL) process, and then transferring it to the desired distribution via regularity of the SL process and conductance arguments. We use this strategy to prove a weak Poincaré inequality (WPI) holds for the Gibbs measure of the Sherrington-Kirkpatrick model when $β< \frac{1}{2}$. A prior result of the authors [arXiv:2605.03718, 2026] proves the ASL process for the Sherrington-Kirkpatrick model satisfies the required regularity conditions. A consequence of the WPI is that a much simpler algorithm -- Glauber dynamics wi…
Apparenté Contexte plus large
Oblivious Sketching of High-Degree Polynomial Kernels
Michael Kapralov, Rasmus Pagh, Ameya Velingker et al. · 2019 · Data Structures and Algorithms · Résumé IA disponible

« Oblivious Sketching » accélère des calculs de noyaux polynomiaux en apprentissage automatique, plutôt que la convergence des méthodes de recherche de zéros.

Résumé scientifique
Kernel methods are fundamental tools in machine learning that allow detection of non-linear dependencies between data without explicitly constructing feature vectors in high dimensional spaces. A major disadvantage of kernel methods is their poor scalability: primitives such as kernel PCA or kernel ridge regression generally take prohibitively large quadratic space and (at least) quadratic time, as kernel matrices are usually dense. Some methods for speeding up kernel linear algebra are known, but they all invariably take time exponential in either the dimension of the input point set (e.g., fast multipole methods suffer from the curse of dimensionality) or in the degree of the kernel functi…
Apparenté Contexte plus large
Potential Hessian Ascent: The Sherrington-Kirkpatrick Model
David Jekel, Juspreet Singh Sandhu, Jonathan Shi · 2024 · Probability · preprint, non relu par les pairs · cité 8 fois · Résumé IA disponible

« Potential Hessian Ascent » propose un algorithme spectral pour optimiser un objectif quadratique sur l’hypercube, non pour trouver des zéros de fonctions analytiques.

Résumé scientifique
We provide the first iterative spectral algorithm to find near-optima of a random quadratic objective over the discrete hypercube. The algorithm is a randomized Hessian ascent in the solid cube, where we modify the objective by subtracting a specific instance-independent potential function [Chen et al., Communications on Pure and Applied Mathematics, 76(7), 2023]. This extends Subag's algorithmic program of Hessian ascent from the sphere [Subag, Communications on Pure and Applied Mathematics, 74(5), 2021] to the more complex geometry of the cube. Utilizing tools from free probability theory, we construct an approximate projector into the top-eigenspaces of the Hessian with well-behaved diago…
Apparenté Contexte plus large
The Hamel-Nadirashvili conjecture for the Fisher-KPP equation
Hongjun Guo, Kelei Wang, Maolin Zhou · 2026 · Analysis of PDEs · Résumé IA disponible

« The Hamel-Nadirashvili conjecture » classe des solutions entières d’équations Fisher-KPP, un problème distinct de la convergence des méthodes de recherche de zéros.

En bref
L’article démontre la conjecture de Hamel–Nadirashvili pour Fisher–KPP à réaction concave : toute solution entière entre 0 et 1 s’approche par des mélanges finis de fronts.
Apparenté Contexte plus large
Matrix anti-concentration inequalities with applications
Zipei Nie · 2021 · Probability · cité 22 fois · Résumé IA disponible

« Matrix anti-concentration inequalities » borne la plus petite valeur singulière de matrices aléatoires, sans traiter l’ordre de convergence des méthodes de recherche de zéros.

Résumé scientifique
We provide a polynomial lower bound on the minimum singular value of an $m\times m$ random matrix $M$ with jointly Gaussian entries, under a polynomial bound on the matrix norm and a global small-ball probability bound $$\inf_{x,y\in S^{m-1}}\mathbb{P}\left(\left|x^* M y\right|>m^{-O(1)}\right)\ge \frac{1}{2}.$$ With the additional assumption that $M$ is self-adjoint, the global small-ball probability bound can be replaced with a weaker version. We establish two matrix anti-concentration inequalities, which lower bound the minimum singular values of the sum of independent positive semidefinite self-adjoint matrices and the linear combination of independent random matrices with independent Ga…
Apparenté Contexte plus large
Fast Multivariate Multipoint Evaluation Over All Finite Fields
Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo et al. · 2022 · Data Structures and Algorithms · cité 21 fois · Résumé IA disponible

« Fast Multivariate Multipoint Evaluation » accélère l’évaluation de polynômes multivariés sur des corps finis, contrairement à l’étude de convergence locale des méthodes de recherche de zéros.

Résumé scientifique
Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field $\mathbb{F}$ that outputs the evaluations of an $m$-variate polynomial of degree less than $d$ in each variable at $N$ points in time \[ (d^m+N)^{1+o(1)}\cdot\poly(m,d,\log|\mathbb{F}|) \] for all $m\in\N$ and all sufficiently large $d\in\mathbb{N}$. A previous work of Kedlaya and Umans (FOCS 2008, SICOMP 2011) achieved the same time complexity when the number of variables $m$ is at most $d^{o(1)}$ and…

Aller plus loin

Comment ces articles sont-ils trouvés ?

Nous comparons le titre et le résumé de cet article avec ceux de tous les articles résumés sur ce site, et avec les articles que Semantic Scholar recommande, ceux qu’il cite et ceux qui le citent (pour un article très cité, ses citations les plus récentes et, depuis OpenAlex, les plus citées). Parmi les travaux antérieurs et les suites, les articles qui s’utilisent en profondeur, une méthode qu’il utilise et les suites très citées remontent un peu. Les niveaux (très proche, proche, apparenté) viennent de la similarité des textes, pas d’un jugement de qualité ; * signale un article sans résumé, comparé par son titre. La phrase sous un article est écrite par une IA à partir des deux résumés : vérifiez-la dans les articles. Un article jugé hors sujet par trois lecteurs quitte la liste.

Mis à jour le 2 novembre 2026.

Avertissement : Notre outil de synthèse basé sur l'IA et l'assistant virtuel fournis sur ce site Web peuvent ne pas toujours fournir des résumés complets ou des réponses exactes. Nous vous encourageons à examiner attentivement et à évaluer le contenu généré pour vous assurer de sa qualité et de sa pertinence par rapport à vos besoins.

Adversarial Wronskians: A proof of the Kung--Traub conjecture

L’essentiel

Question

Méthode

Résultats

Limites

Portée

Pour aller plus loin

Definitions

Adversarial Wronskians : une borne fondamentale pour la recherche de racines

Une question sur la vitesse de convergence

La borne : 2n − 1

Comment construire un contre-exemple qui dure

Des observations qui laissent des possibilités ouvertes

Des corrections successives et une fonction unique

Une borne optimale et des observations par groupes

Pourquoi ce résultat compte

Posez des questions sur cet article à notre assistant IA

Outils pour cet article

Outils avancés Premium

Les articles autour de celui-ci

Les articles les plus proches

Aller plus loin

Citer cet article (BibTeX)