TL;DR
A 2021 blog post demonstrates using quantifier elimination (via the Tarski–Seidenberg theorem and QEPCAD through SageMath) to mechanically settle many competition-style polynomial (in)equalities. The author shows worked examples that verify inequalities, locate equality cases, and extract geometric descriptions of solution sets.
What happened
A blog post from 22 December 2021 explains how quantifier elimination can be used to resolve many contrived inequalities that appear in competition mathematics. The post recalls the Tarski–Seidenberg result that formulas built from polynomial equalities and inequalities with logical connectives and quantifiers over the reals can be transformed into equivalent quantifier-free formulas. Practically, the author uses SageMath’s interface to QEPCAD to run quantifier-elimination queries. He demonstrates checking an inequality under the constraint a,b ≥ 0 and a^4 + b^4 = 17, showing the implication returns TRUE and extracting the two equality solutions (a,b) = (2,1) and (1,2). A second example checks a three-variable product inequality after clearing denominators, and the author uses QEPCAD’s geometric solution output to describe where equality holds. The post also notes installation steps for QEPCAD in Sage and mentions additional QEPCAD features and external applications of the technique.
Why it matters
- Automates verification of many polynomial (in)equalities that commonly appear in contest problems, saving manual algebraic work.
- Can produce quantifier-free equivalents or counterexamples, aiding both learning and research by making truth conditions explicit.
- Provides ways to locate equality cases or describe solution geometry, which helps identify sharpness and structure of inequalities.
- Connects model-theoretic results (Tarski–Seidenberg) to practical tools researchers and students can run in SageMath.
Key facts
- The post was published on 22 December 2021.
- It relies on the Tarski–Seidenberg theorem: formulas built from polynomial equalities/inequalities and quantifiers over the reals admit equivalent quantifier-free formulas.
- The author uses SageMath’s interface to QEPCAD to perform quantifier elimination and to evaluate logical formulas.
- To install QEPCAD for Sage the post suggests running: sage -i qepcad.
- Example 1: under a,b ≥ 0 and a^4 + b^4 = 17, the inequality (rewritten as (15(a+b)-17)^2 ≥ 14^2 * 2 * a * b) is verified by QEPCAD as TRUE.
- For that example QEPCAD returned the equality solutions {'a': 2, 'b': 1} and {'a': 1, 'b': 2} when asked for all points.
- Example 2: the inequality (x+1/x)(y+1/y)(z+1/z) ≥ (x+1/y)(y+1/z)(z+1/x) for positive x,y,z is checked true after multiplying both sides by xyz, and QEPCAD can output a geometric description of the equality locus.
- QEPCAD supports additional query forms such as counting exact numbers of solutions, asking for infinite solutions, and testing connectedness (described as “bonus quantifiers” in the post).
- The post cites external usage: André Platzer uses related automated methods in work on cyber-physical systems (referenced book and lectures).
What to watch next
- Ensure polynomial form before querying: non-polynomial expressions may need algebraic manipulation (the post multiplies by xyz to clear denominators).
- Sage parsing quirks: the author reports an instance where typing a formula didn’t parse as expected and switching to constructor functions resolved it.
- Scalability and runtime for large or high-degree systems: not confirmed in the source.
- Limits of the tool for non-polynomial or domain-restricted problems: not confirmed in the source.
Quick glossary
- Quantifier elimination: A process that transforms a logical formula with existential or universal quantifiers into an equivalent formula without quantifiers, typically over a specified structure such as the real numbers.
- Tarski–Seidenberg theorem: A model-theoretic result stating that sets definable by polynomial equalities and inequalities with quantifiers over the real numbers have equivalent descriptions without quantifiers; projections of semialgebraic sets are semialgebraic.
- QEPCAD: A software tool for performing quantifier elimination and related computations over real closed fields; it can be invoked from interfaces such as SageMath.
- SageMath (Sage): An open-source mathematics software system that integrates many specialized libraries and tools for algebra, geometry, number theory, and more; it can call QEPCAD for quantifier-elimination tasks.
Reader FAQ
What kinds of formulas can QEPCAD handle?
Per the Tarski–Seidenberg framework in the post, QEPCAD handles formulas built from polynomial equalities and inequalities with logical connectives and quantifiers over the reals.
How do I install QEPCAD for Sage?
The post suggests running the Sage package installer command: sage -i qepcad.
Can QEPCAD find where equality holds, not just truth values?
Yes; the post shows using options like solution='all-points' and solution='geometric' to extract equality solutions or geometric descriptions.
Is QEPCAD appropriate for non-polynomial inequalities as-is?
Not directly—examples in the post first rewrite expressions into polynomial form (for instance, by multiplying through by xyz); otherwise this is not confirmed in the source.
How well does this scale to very large or high-degree problems?
not confirmed in the source
Slaughtering Competition Problems with Quantifier Elimination 22 DEC 2021 – TAGS: SAGE , FEATURED Anytime I see questions on mse that ask something “simple”, I feel a powerful urge to…
Sources
- Slaughtering Competition Problems with Quantifier Elimination
- Sage | Chris Grossack's Blog
- Interface to QEPCAD
- Modality in Dialogue: Planning, Pragmatics and Computation
Related posts
- Unity’s Mono runtime falls behind modern .NET — why your C# runs much slower
- Parsing IP Addresses Quickly and Portably – Without SIMD Magic Techniques
- Why You Should Keep AI Out of Your Cognitive ‘Gym’ — A Practical 2026 Rule