Modular Arithmetic Challenge | What's new
What's new Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao
Home
About
Career advice
On writing
Books
Mastodon+
Applets
Subscribe to feed
Modular Arithmetic Challenge
8 June, 2026 in math.NA | Tags: Alberto Alfarano, Cathy Li, Emily Wenger, Francois Charton, Kristin Lauter, modular arithmetic, SAIR, Yongzheng Jia | by Terence Tao
A couple months ago, Damek Davis and I launched the first mathematical challenge at the SAIR Foundation, aimed at "distilling" the ability to solve 22 million problems in universal algebra into a condensed form. Stage one of that challenge has now been completed, with several effective "cheat sheets" generated to guess the truth or falsity of these problems to reasonable accuracy; the leaderboard for that stage, with their winning cheatsheets can be found here. Stage two of that challenge, in which the competitors now have access to Python code as well as modest LLMs, and now need to generate Lean proofs or disproofs rather than just true-false answers, is currently underway.
With Alberto Alfarano, François Charton, Yongzheng Jia, Kristin Lauter, Cathy Li, and Emily Wenger, are launching a second challenge at SAIR, this time focused on seeing how efficiently neural networks can execute simple modular arithmetic operations. For this challenge we are focusing on the simple operation of modular multiplication: taking a prime modulus (up to about a thousand digits long) and two integers and between and , and computing the product . This is of course a solved problem using traditional computation, being a single line of code in any modern programming language. But it has been a fascinating toy problem in which to explore the basic capabilities of neural networks.
For instance, this problem has revealed the mysterious phenomenon of "grokking". When one tries to train a neural network on this problem for small sizes of inputs , then initially one runs into the familiar problem of overfitting: the network learns to solve the problem for the training data too well, at the expense of performing well for held-out test data. However, if one continues training for sufficiently long periods of time, then the network can suddenly "grok" the problem and generalize surprisingly well to the test data. It appears that the neural network can suddenly "learn" powerful computational tricks, such as taking discrete logarithms, to find accurate and efficient ways to arrive at the correct answer.
This challenge is not about grokking, but instead about scaleability: we can create neural network models for modular multiplication that are extremely accurate for, say, 10-bit inputs, but they struggle at handling larger bit sizes. The competition is then simple: submit a neural network (with fixed weights) that can solve this task for larger input sizes with as high an accuracy as possible. Some pre-processing of the individual inputs , , is permitted (e.g., to convert these numbers into decimal or some other convenient representation), but other than that the main computation has to be neural in nature; one cannot simply run some Python code, for instance, to compute the multiplication. We are imposing limits on the size and allocated run time on the neural network, but otherwise we are deliberately being flexible in the architecture requirements, in order to encourage creative experimentation; in particular, we permit networks whose weights were arrived at by other means than the usual machine learning training process.
This is a relatively simple challenge to state, but we genuinely do not know what to expect from the competitor entries – is there a clever way to encode modular arithmetic for even quite large numbers into a medium size neural network, or is it going to be an exceptionally difficult task? Hopefully we will find out in a few months!
Share this:
Print (Opens in new window)<br>Print
Email a link to a friend (Opens in new window)<br>Email
More
Share on X (Opens in new window)
Share on Facebook (Opens in new window)<br>Facebook
Share on Reddit (Opens in new window)<br>Reddit
Share on Pinterest (Opens in new window)<br>Pinterest
Like Loading...
Recent Comments
Terence Tao on Primitive sets and von Mangold…Terence Tao on Primitive sets and von Mangold…Anonymous on 275A, Notes 0: Foundations of…Anonymous on Primitive sets and von Mangold…Anonymous on Primitive sets and von Mangold…Terence Tao on 275A, Notes 4: The central lim…Anonymous on 275A, Notes 4: The central lim…Terence Tao on 245B, Notes 12: Continuous fun…Terence Tao on 275A, Notes 0: Foundations of…Terence Tao on 245A, Notes 3: Integration on…Terence Tao on 245B, notes 3: L^p spacesAnonymous on 245B, Notes 12: Continuous fun…Anonymous on 275A, Notes 0: Foundations of…Anonymous on 245A, Notes 3: Integration on…Anonymous on 245B, notes 3: L^p spaces
Top Posts<br>Career advice<br>Primitive sets and von Mangoldt chains:...