Learning to Prove Trigonometric Identities

Zhou Liu, Yujun Li, Zhengying Liu, Lin Li, Zhenguo LiarXiv 2022 · DOI · arXiv

Abstract

Automated Theorem Proving (ATP) faces significant challenges in handling combinatorial explosions and a lack of high-quality training data. This paper introduces AutoTrig, a deep learning-based prover for trigonometric identities developed by researchers at Huawei Noah’s Ark Lab. By integrating imitation learning from a pruned search strategy with reinforcement learning (PPO), AutoTrig achieves near-optimal proof lengths while operating 1,000 times faster than traditional search methods. The system demonstrates a 99.8% pass rate on synthetic datasets and outperforms both symbolic tools and human experts.

Introduction

Automated Theorem Proving is a fundamental goal of symbolic AI. However, it is hindered by the "combinatorial explosion" of deduction steps and the difficulty of generalizing to unseen problems. Trigonometric identities provide an ideal domain to test these challenges, as they require "mathematical intuition"—the ability to choose the most efficient path among many valid transformations. While tools like Sympy or Matlab can solve many identities, they often rely on heuristics that fail to find the most elegant or shortest proofs.

Methodology

The AutoTrig pipeline consists of several key stages designed to transform raw expressions into optimized proofs.

Data Generation and Normalization

To address the scarcity of human-proven data, the authors developed a "bottom-up" synthetic generator. Expressions are first normalized into a standard polynomial form using $\sin$ and $\cos$. The generator starts with a simple expression, applies random transformations to create a complex equivalent, and subtracts them to form an identity equal to zero.

Search and Learning Architecture

Initial "ground truth" proofs are generated using rBFS (Random Breadth-First Search), which prunes the search tree by exploring only three random branches per node. The core architecture utilizes a BERT (Transformer) backbone to process mathematical expressions as token sequences.

Training Pipeline

The training process involves two main phases:

  1. Imitation Learning (IL): The model is trained to mimic successful paths from rBFS. Theoretical analysis suggests the model can outperform its teacher by aggregating patterns across diverse samples.
  2. Reinforcement Learning (RL): Using Proximal Policy Optimization (PPO), the model is refined to minimize proof length. It receives rewards for successful proofs and penalties for each step taken.
The AutoTrig training and inference pipeline, illustrating the flow from identity generation to reinforcement learning.

Evaluation and Results

AutoTrig was evaluated against synthetic datasets (200,000 identities), shuffled terms (T1), unseen coefficients (T2), and real-world IMO-level problems (T3).

Efficiency and Quality

AutoTrig demonstrates a massive speedup, proving identities in an average of 0.159 seconds, compared to 166 seconds for a full BFS. Despite this speed, proof quality remains high; AutoTrig's average proof length of 4.40 steps is close to the theoretical minimum of 4.27 steps and significantly better than the rBFS teacher (4.94 steps).

Comparative Performance

AutoTrig achieved a 99.8% pass rate on synthetic tests, surpassing Sympy (90.5%) and Matlab (96.8%). In a comparative study with human experts (Master's degree or higher), AutoTrig found shorter proofs (5.6 steps vs. 7.58 steps) in a fraction of the time.

Performance metrics comparing Imitation Learning (Model-IL) and Reinforcement Learning (AutoTrig), showing improvements in pass rate and proof length during training.

Discussion and Key Insights

A significant finding is the model's ability to learn the "min" operator. By training on sub-optimal rBFS data, the neural network learns to identify the best actions across many examples, effectively distilling an optimal policy. Through RL, the agent develops "mathematical intuition," such as identifying common factors early to reduce proof length.

Limitations and Future Work

Current limitations include a fixed sequence length in BERT (limiting expressions to 8 terms) and a restricted set of 8 transformation rules. Future work aims to expand the system to handle multivariable identities, complex summations, and a broader range of mathematical "tricks" required for high-level competition problems.

Summary updated

Abstract

Automatic theorem proving with deep learning methods has attracted attentions recently. In this paper, we construct an automatic proof system for trigonometric identities. We define the normalized form of trigonometric identities, design a set of rules for the proof and put forward a method which can generate theoretically infinite trigonometric identities. Our goal is not only to complete the proof, but to complete the proof in as few steps as possible. For this reason, we design a model to learn proof data generated by random BFS (rBFS), and it is proved theoretically and experimentally that the model can outperform rBFS after a simple imitation learning. After further improvement through reinforcement learning, we get AutoTrig, which can give proof steps for identities in almost as short steps as BFS (theoretically shortest method), with a time cost of only one-thousandth. In addition, AutoTrig also beats Sympy, Matlab and human in the synthetic dataset, and performs well in many generalization tasks.
BibTeX
@misc{liu2022learning,
  author = {Zhou Liu and Yujun Li and Zhengying Liu and Lin Li and Zhenguo Li},
  title = {{Learning to Prove Trigonometric Identities}},
  year = {2022},
  eprint = {2207.06679},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2207.06679},
}
Figure