Uma ferramenta de prova de conceito para verificar as estimativas

2 de maio de 2025

5

Este submit foi inspirado por algumas discussões recentes com o Bjoern Bringmann.

Os pacotes simbólicos de software program de matemática são altamente desenvolvidos para muitas tarefas matemáticas em áreas como álgebra, cálculo e análise numérica. No entanto, até onde eu sei, não temos ferramentas igualmente sofisticadas para verificar as estimativas assintóticas – desigualdades que deveriam manter para parâmetros arbitrariamente grandes, com perdas constantes. Particularmente importantes são estimativas funcionais, onde os parâmetros envolvem uma função ou sequência desconhecida (vivendo em algum espaço de função adequado, como um espaço); Mas, para esta discussão, focarei na situação mais simples de estimativas assintóticas que envolvem um número finito de números reais positivos, combinados usando operações aritméticas, como adição, multiplicação, divisão, exponenciação e mínimo e máximo (mas sem subtração). Uma desigualdade típica aqui pode ser a fraca desigualdade média aritmética-geométrica

$DisplayStyle (ABC)^{1/3} LESSIM A+B+C (1)$

onde ${abc}$ são números reais positivos arbitrários e os ${ Lesssim}$ Aqui indica que estamos dispostos a perder uma constante não especificada nas estimativas.

Eu desejei no passado (por exemplo, Nesta resposta MathOverflow) para uma ferramenta que poderia determinar automaticamente se essa estimativa period verdadeira ou não (e fornecer uma prova se for verdade ou um contra -exemplo assintótico se false). Em princípio, as desigualdades simples dessa forma podem ser resolvidas automaticamente pela divisão de casos de força bruta. Por exemplo, com (1)um primeiro observa que ${a+b+c}$ é comparável a ${ max (a, b, c)}$ até constantes, por isso basta determinar se

$DisplayStyle (ABC)^{1/3} LESSIM MAX (A, B, C). (2)$

Em seguida, para resolver o máximo, pode -se dividir em três casos: ${a gtrSim b, c}$ ; ${b gtrsim a, c}$ ; e ${c gtrsim a, b}$ . Suponha que, por exemplo, que ${a gtrSim b, c}$ . Então a estimativa para provar simplifica para

$DisplayStyle (ABC)^{1/3} LESSIM A,$

e este é (depois de tomar logaritmos) uma combinação linear positiva das hipóteses ${a gtrSim b}$ Assim, ${a gtrSim C}$ . A tarefa de determinar essa combinação linear é uma tarefa de programação linear padrão, para a qual existem muitos pacotes de software program de computador.

Qualquer desigualdade não é muito difícil de resolver manualmente, mas há aplicações nas quais é preciso verificar um grande número dessas desigualdades ou dividir em um grande número de casos. Vou dar um exemplo aleatoriamente de um Papel antigo meu (adaptado da equação após (51) e ignorando alguns termos de epsilon para simplificar): eu queria estabelecer a estimativa

$DisplayStyle frac { Langle n_2 rangle^{1/2}} { Langle n_1 rangle^{1/4} l_1^{1/2} l_2^{1/2}} l _ {}}}^{12 {1/2 {1/2}} l _ {}} {1/2 {1/2 {1/2}} l _ {}}^{1/2 N_3)^{1/2} LESSIM 1 (3)$

para qualquer ${N_1, n_2, n_3, l_1, l_2, l_3> 0}” class=”latex” /> obedecer às restrições</p> <p class=$ $displaystyle n _ { max} sim n _ { mathrm {med}} sim n; quad l _ { max} sim l _ { mathrm {med}} gtrsim n_1 n_2 n_3$

onde ${N _ { max}}$ Assim, ${N _ { mathrm {med}}}$ e ${N _ { min}}$ são o máximo, mediano e o mínimo de ${N_1, n_2, n_3}$ respectivamente, e da mesma forma ${L _ { max}}$ Assim, ${L _ { mathrm {med}}}$ e ${L _ { min}}$ e ${ langle n rangle: = (1+n^2)^{1/2}}$ . Esse limite em specific pode ser despachado em três ou quatro linhas de algumas desigualdades mais simples; Mas levou algum tempo para criar essas desigualdades, e eu tive que fazer uma dúzia de desigualdades adicionais desse tipo. Esta é uma tarefa que parece extremamente madura para a automação, principalmente com a tecnologia moderna.

Recentemente, tenho feito muito mais codificação (em Python, principalmente) do que no passado, auxiliado pela notável instalação de grandes modelos de idiomas para gerar amostras iniciais de código para muitas tarefas diferentes ou para preenchimento automático de código parcialmente escrito. Na maioria das vezes, me restringi a tarefas de codificação bastante simples, como calcular e, em seguida, plotar algumas funções matemáticas levemente complicadas ou fazer alguma análise de dados rudimentares em algum conjunto de dados. Mas decidi me dar a tarefa mais desafiadora de codificar um verificador que poderia lidar com as desigualdades da forma acima. Após cerca de quatro horas de codificação, com assistência frequente de um LLMPude produzir uma ferramenta de prova de conceito para isso, que pode ser encontrada em Este repositório do GitHub. Por exemplo, para verificar (1)o código Python relevante é

    a = Variable("a")
    b = Variable("b")
    c = Variable("c")
    assumptions = Assumptions()
    assumptions.can_bound((a * b * c) ** (1 / 3), max(a, b, c))

e a saída (um tanto detalhada) verificando a desigualdade é

Checking if we will sure (((a * b) * c) ** 0.3333333333333333) by max(a, b, c) from the given axioms.
We are going to cut up into the next instances:
((b <~ a, c <~ a), (a <~ b, c <~ b), (a <~ c, b <~ c))
Attempting case: ((b <~ a, c <~ a),)
Simplify to proving (((a ** 0.6666666666666667) * (b ** -0.3333333333333333)) * (c ** -0.3333333333333333)) >= 1.
Certain was confirmed true by multiplying the next hypotheses :
b <~ a raised to energy 0.33333333
c <~ a raised to energy 0.33333333
Attempting case: ((a <~ b, c <~ b),)
Simplify to proving (((b ** 0.6666666666666667) * (a ** -0.3333333333333333)) * (c ** -0.3333333333333333)) >= 1.
Certain was confirmed true by multiplying the next hypotheses :
a <~ b raised to energy 0.33333333
c <~ b raised to energy 0.33333333
Attempting case: ((a <~ c, b <~ c),)
Simplify to proving (((c ** 0.6666666666666667) * (a ** -0.3333333
333333333)) * (b ** -0.3333333333333333)) >= 1.
Certain was confirmed true by multiplying the next hypotheses :
a <~ c raised to energy 0.33333333
b <~ c raised to energy 0.33333333
Certain was confirmed true in all instances!

É claro que isso é uma prova extremamente deselegante, mas a elegância não é o ponto aqui; Pelo contrário, é automatizado. (Veja também isso Artigo recente de Heather Macbeth Para como os estilos de redação de prova mudam na presença de ferramentas automatizadas, como assistentes formais de prova.)

O código está próximo de também ser capaz de lidar com estimativas mais complicadas, como (3); No momento, não escrevi código para lidar adequadamente com hipóteses como ${N _ { max} sim n _ { mathrm {med}} sim n}$ que envolvem expressões complexas, como ${N _ { max} = max (n_1, n_2, n_3)}$ em oposição a hipóteses que envolvem apenas variáveis atômicas, como ${N_1}$ Assim, ${N_2, n_3}$ mas posso pelo menos lidar com expressões tão complexas nos lados esquerdo e direito da estimativa que estou tentando verificar.

De qualquer forma, o código, sendo uma mistura de código gerado por LLM e minhas próprias habilidades rudimentares do Python, dificilmente é um exemplo de codificação eficiente ou elegante, e tenho certeza de que existem muitos programadores especializados que podem fazer um trabalho muito melhor. Mas acho que isso é prova de conceito de que uma ferramenta mais sofisticada desse formulário poderia ser prontamente criada para realizar tarefas mais avançadas. Uma tarefa de exemplo foi a que eu dei na questão acima do MathOverflow, ou seja, capaz de verificar automaticamente uma reivindicação como

$displaystyle sum_ {d = 0}^ infty frac {2d + 1} {2h^2 (1 + frac {d (d + 1)} {h^2}) (1 + frac {d (d + 1)} {h^2m^2})$

automaticamente para todos ${h, m> 0}” class=”latex” />. Outra tarefa seria verificar automaticamente a capacidade de estimar alguma expressão multilinear de várias funções, em termos de normas de tais funções em espaços padrão, como espaços Sobolev; Esta é uma tarefa particularmente prevalente na análise de PDE e harmônicos (e pode francamente ficar um tanto tediosa à mão). Conforme especulado nesse posto de MO, pode-se esperar também utilizar a IA para ajudar no processo de verificação, por exemplo, sugerindo possíveis divisões das várias somas ou integrais envolvidas, mas isso seria um objetivo de longo prazo.</p> <p>Esse tipo de desenvolvimento de software program provavelmente seria melhor realizado como um projeto colaborativo, envolvendo matemáticos e programadores especializados. Eu estaria interessado em receber conselhos sobre a melhor forma de prosseguir com esse projeto (por exemplo, faria sentido incorporar essa ferramenta em uma plataforma existente como Sagemath) e quais recursos para um verificador de estimativa geral seria mais desejável para os matemáticos. One factor on my wishlist is the power to provide a device an expression to estimate (akin to a multilinear integral of some unknown features), in addition to a set set of instruments to sure that integral (eg, splitting the integral into items, integrating by elements, utilizing the Hölder and Sobolev inequalities, and so forth.), and have the pc do its finest to optimize the sure it could actually produce with these instruments (full with some independently verifiable Certificado de prova para sua saída). Também é possível imaginar essas ferramentas tendo a opção de gerar seus certificados de prova em um idioma de assistente de prova formal, como o LEAN. Mas talvez existam outros recursos úteis que os leitores desejam propor. </p> </p></div> <div class=$