Close Menu
    Join Us Now
    Maths

    A proof of concept tool to verify estimates

    Help MathsXP.com By No Comments6 Mins Read
    A proof of concept tool to verify estimates

    This post was inspired by some recent discussions with Bjoern Bringmann.

    Symbolic math software packages are highly developed for many mathematical tasks in areas such as algebra, calculus, and numerical analysis. However, to my knowledge we do not have similarly sophisticated tools for verifying asymptotic estimates – inequalities that are supposed to hold for arbitrarily large parameters, with constant losses. Particularly important are functional estimates, where the parameters involve an unknown function or sequence (living in some suitable function space, such as an space); but for this discussion I will focus on the simpler situation of asymptotic estimates involving a finite number of positive real numbers, combined using arithmetic operations such as addition, multiplication, division, exponentiation, and minimum and maximum (but no subtraction). A typical inequality here might be the weak arithmetic mean-geometric mean inequality

    \displaystyle (abc)^{1/3} \lesssim a+b+c \ \ \ \ \ (1)


     where {a,b,c} are arbitrary positive real numbers, and the {\lesssim} here indicates that we are willing to lose an unspecified constant in the estimates.

    I have wished in the past (e.g., in this MathOverflow answer) for a tool that could automatically determine whether such an estimate was true or not (and provide a proof if true, or an asymptotic counterexample if false). In principle, simple inequalities of this form could be automatically resolved by brute force case splitting. For instance, with (1), one first observes that {a+b+c} is comparable to {\max(a,b,c)} up to constants, so it suffices to determine if

    \displaystyle (abc)^{1/3} \lesssim \max(a,b,c). \ \ \ \ \ (2)

    Next, to resolve the maximum, one can divide into three cases: {a \gtrsim b,c}; {b \gtrsim a,c}; and {c \gtrsim a,b}. Suppose for instance that {a \gtrsim b,c}. Then the estimate to prove simplifies to

    \displaystyle (abc)^{1/3} \lesssim a,

    and this is (after taking logarithms) a positive linear combination of the hypotheses {a \gtrsim b}, {a \gtrsim c}. The task of determining such a linear combination is a standard linear programming task, for which many computer software packages exist.

    Any single such inequality is not too difficult to resolve by hand, but there are applications in which one needs to check a large number of such inequalities, or split into a large number of cases. I will take an example at random from an old paper of mine (adapted from the equation after (51), and ignoring some epsilon terms for simplicity): I wanted to establish the estimate

    \displaystyle \frac{\langle N_2 \rangle^{1/2}}{\langle N_1 \rangle^{1/4} L_1^{1/2} L_2^{1/2} } L_{\min}^{1/2} N^{-1} (N_1 N_2 N_3)^{1/2} \lesssim 1 \ \ \ \ \ (3)

    for any {N_1,N_2,N_3,L_1,L_2,L_3 > 0} obeying the constraints

    \displaystyle N_{\max} \sim N_{\mathrm{med}} \sim N; \quad L_{\max} \sim L_{\mathrm{med}} \gtrsim N_1 N_2 N_3

    where {N_{\max}}, {N_{\mathrm{med}}}, and {N_{\min}} are the maximum, median, and minimum of {N_1, N_2, N_3} respectively, and similarly for {L_{\max}}, {L_{\mathrm{med}}}, and {L_{\min}}, and {\langle N \rangle := (1+N^2)^{1/2}}. This particular bound could be dispatched in three or four lines from some simpler inequalities; but it took some time to come up with those inequalities, and I had to do a dozen further inequalities of this type. This is a task that seems extremely ripe for automation, particularly with modern technology.

    Recently, I have been doing a lot more coding (in Python, mostly) than in the past, aided by the remarkable facility of large language models to generate initial code samples for many different tasks, or to autocomplete partially written code. For the most part, I have restricted myself to fairly simple coding tasks, such as computing and then plotting some mildly complicated mathematical functions, or doing some rudimentary data analysis on some dataset. But I decided to give myself the more challenging task of coding a verifier that could handle inequalities of the above form. After about four hours of coding, with frequent assistance from an LLM, I was able to produce a proof of concept tool for this, which can be found at this Github repository. For instance, to verify (1), the relevant Python code is 

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

    and the (somewhat verbose) output verifying the inequality is 

    Checking if we can bound (((a * b) * c) ** 0.3333333333333333) by max(a, b, c) from the given axioms.
We will split into the following cases:
[[b = 1.
Bound was proven true by multiplying the following hypotheses :
b = 1.
Bound was proven true by multiplying the following hypotheses :
a = 1.
Bound was proven true by multiplying the following hypotheses :
a

    This is of course an extremely inelegant proof, but elegance is not the point here; rather, that it is automated. (See also this recent article of Heather Macbeth for how proof writing styles change in the presence of automated tools, such as formal proof assistants.)

    The code is close to also being able to handle more complicated estimates such as (3); right now I have not written code to properly handle hypotheses such as {N_{\max} \sim N_{\mathrm{med}} \sim N} that involve complex expressions such as {N_{\max} = \max(N_1,N_2,N_3)}, as opposed to hypotheses that only involve atomic variables such as {N_1}, {N_2, N_3}, but I can at least handle such complex expressions in the left and right-hand sides of the estimate I am trying to verify.

    In any event, the code, being a mixture of LLM-generated code and my own rudimentary Python skills, is hardly an exemplar of efficient or elegant coding, and I am sure that there are many expert programmers who could do a much better job. But I think this is proof of concept that a more sophisticated tool of this form could be quite readily created to do more advanced tasks. One such example task was the one I gave in the above MathOverflow question, namely being able to automatically verify a claim such as

    \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})^2} \lesssim 1 + \log(m^2)

    automatically for all {h,m > 0}. Another task would be to automatically verify the ability to estimate some multilinear expression of various functions, in terms of norms of such functions in standard spaces such as Sobolev spaces; this is a task that is particularly prevalent in PDE and harmonic analysis (and can frankly get somewhat tedious to do by hand). As speculated in that MO post, one could eventually hope to also utilize AI to assist in the verification process, for instance by suggesting possible splittings of the various sums or integrals involved, but that would be a long-term objective.

    This sort of software development would likely best be performed as a collaborative project, involving both mathematicians and expert programmers. I would be interested to receive advice on how best to proceed with such a project (for instance, would it make sense to incorporate such a tool into an existing platform such as SageMATH), and what features for a general estimate verifier would be most desirable for mathematicians. One thing on my wishlist is the ability to give a tool an expression to estimate (such as a multilinear integral of some unknown functions), as well as a fixed set of tools to bound that integral (e.g., splitting the integral into pieces, integrating by parts, using the Hölder and Sobolev inequalities, etc.), and have the computer do its best to optimize the bound it can produce with those tools (complete with some independently verifiable proof certificate for its output). One could also imagine such tools having the option to output their proof certificates in a formal proof assistant language such as Lean. But perhaps there are other useful features that readers may wish to propose.


    Source link

    Share.

    Related Posts

    Add A Comment

    Comments are closed.