Misfortunes of a mathematicians' trio using Computer Algebra Systems: Can we trust?

Basic Information

• Paper ID: 1312.3270
• Title: Misfortunes of a mathematicians' trio using Computer Algebra Systems: Can we trust?
• Authors: Antonio J. Durán (Universidad de Sevilla), Mario Pérez (Universidad de Zaragoza), Juan L. Varona (Universidad de La Rioja)
• Classification: cs.SC (Symbolic Computation), cs.MS (Mathematical Software)
• Publication Date: October 15, 2013 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/1312.3270

Abstract

Computer algebra systems provide substantial assistance to mathematical research, yet unexpected software errors can sometimes severely impact research outcomes. As an illustration, the authors demonstrate how they detected an error in Mathematica's computation of integer matrix determinants: not only does it calculate the determinant incorrectly, but computing the same determinant twice yields different results.

Research Background and Motivation

1. Problem to be Addressed: The authors discovered serious errors in Mathematica when computing determinants of large integer matrices during mathematical research, including incorrect computational results and inconsistent results from identical computations.
2. Problem Significance:
   • Mathematicians increasingly rely on computer algebra systems for research
   • Incorrect computational results may lead to erroneous mathematical conclusions
   • Large integer computation is critically important in fields such as cryptography
3. Limitations of Existing Methods:
   • Commercial computer algebra systems are "black boxes" with opaque algorithms
   • Known errors are typically not disclosed to users
   • Modern software verification techniques are difficult to apply
4. Research Motivation: While extending results by Karlin and Szegő on orthogonal polynomials, the authors discovered that Mathematica and Maple produced different computational results, prompting deeper investigation that revealed systematic errors in Mathematica.

Core Contributions

1. Discovery and Reporting of Serious Computational Errors in Mathematica: Erroneous results in computing determinants of large integer matrices
2. Provision of Reproducible Error Generation Methods: Design of a randomized program to generate matrices that trigger the error
3. Revelation of Non-deterministic Error Characteristics: The same matrix's determinant computation may produce different results
4. Questioning the Trustworthiness of Computer Algebra Systems: Raises important discussion on how to trust these systems

Methodology Details

Problem Discovery Process

While researching the Casorati determinant of orthogonal polynomials: $\det \begin{pmatrix} P_{f_1}(a_k) & P_{f_1}(a_{k+1}) & \cdots & P_{f_1}(a_{k+l}) \\ P_{f_2}(a_k) & P_{f_2}(a_{k+1}) & \cdots & P_{f_2}(a_{k+l}) \\ \vdots & \vdots & \ddots & \vdots \\ P_{f_l}(a_k) & P_{f_l}(a_{k+1}) & \cdots & P_{f_l}(a_{k+l}) \end{pmatrix}$

By constructing all examples using integers to avoid floating-point issues, the authors discovered that Mathematica and Maple produced different results.

Error Isolation Method

To isolate the computational problem, the authors designed the following method to generate matrices that trigger the error:

1. Generate Base Matrix:

   basicMatrix = Table[Table[RandomInteger[{-99, 99}], {i, 1, 14}], {j, 1, 14}]
   

2. Create Large Integers:

   powersMatrix = DiagonalMatrix[{10^123, 10^152, 10^185, 10^220, 10^397,
   10^449, 10^503, 10^563, 10^979, 10^1059, 10^1143, 10^1229, 10^1319, 10^1412}]
   

3. Add Random Perturbations:

   smallMatrix = Table[Table[RandomInteger[{-999, 999}], {i, 1, 14}], {j, 1, 14}]
   

4. Construct Final Matrix:

   bigMatrix = basicMatrix.powersMatrix + smallMatrix
   

Error Verification

Verification through multiple computations of the same matrix's determinant:

a = Det[bigMatrix];
b = Det[bigMatrix];

Results showed that a==b frequently returned False.

Experimental Setup

Test Environment

• Software Versions: Mathematica 8.0 to 9.0.1
• Operating Systems: Mac and Windows
• Comparison Software: Maple and Sage as verification tools

Test Data

• Matrix Size: 14×14
• Numerical Range: Large integers containing approximately 10,000 digits
• Generation Method: Randomly generated base matrices, then constructed through power amplification and small perturbations

Experimental Results

Main Findings

1. Computational Error: The determinant computed by Mathematica is completely incorrect
2. Non-determinism: Multiple computations of the same matrix produce different results
3. Version Dependency: Errors appear in versions 8 and 9, while versions 6 and 7 appear unaffected

Specific Case Study

In one concrete example:

• Mathematica first computation: N[a] = -3.263388173990166 × 10^9768
• Mathematica second computation: N[b] = -8.158470434975415 × 10^9768
• Correct result (Maple/Sage): ≈ 1.95124219131987 × 10^9762

Error Report

The authors reported the error to Wolfram Research on October 7, 2013 (Case Number: CASE:303438), received confirmation, but the issue remained unresolved in subsequent versions.

Related Work

1. Historical Precedent: Similar to the Pentium division error discovered by Thomas Nicely in 1994
2. Software Verification: References verification techniques research for open-source computer algebra systems
3. Successful Mathematical Software Cases:
   • Four Color Theorem proof (Appel and Haken)
   • Kepler Conjecture proof (Thomas Hales)
   • Kenzo software discovering errors in published theorems

Conclusions and Discussion

Main Conclusions

1. Trustworthiness Issues: Even symbolic computation (integer arithmetic) in computer algebra systems may produce errors
2. Scope of Impact: Large integer computation errors affect not only theoretical mathematics but also applied fields such as cryptography
3. Systemic Problem: The "black box" nature of commercial software makes errors difficult to predict and avoid

Limitations

1. Unclear Error Triggering Conditions: Cannot precisely predict which matrices will trigger errors
2. Version Specificity: Errors appear only in specific versions
3. Platform Dependency: Verification required across different operating systems

Future Directions

1. Develop improved software verification techniques
2. Enhance transparency of commercial software
3. Establish more comprehensive error reporting and fixing mechanisms

In-Depth Evaluation

Strengths

1. Significant Practical Value: Reveals serious errors in widely-used mathematical software
2. Scientific Methodology: Verification through multiple independent systems ensures reliability of findings
3. Strong Reproducibility: Provides detailed methods for error reproduction
4. Clear Writing: Vividly demonstrates the problem discovery process through concrete mathematical research background

Weaknesses

1. Limited Theoretical Analysis: Lacks deep analysis of the fundamental causes of errors
2. Lack of Solutions: Primarily a problem report, lacking methods for preventing or detecting such errors
3. Limited Test Scope: Focuses mainly on one specific type of computation (large integer matrix determinants)

Impact

1. Academic Value: Alerts researchers to reliability issues in computer-assisted proofs
2. Practical Value: Important warning for users relying on Mathematica for large integer computations
3. Software Improvement: Motivates software developers to address and fix such errors

Applicable Scenarios

The findings of this research apply to:

• Research using Mathematica for large integer matrix computations
• Large number operations in cryptography
• Mathematical research requiring high-precision symbolic computation
• Reliability assessment of computer algebra systems

References

The paper cites the following important literature:

1. Karlin & Szegő (1960/1961) - Original research on orthogonal polynomial determinants
2. Appel & Haken (1977) - Computer-assisted proof of the Four Color Problem
3. Hales (2005) - Proof of the Kepler Conjecture
4. Ciaurri & Varona (2006) - Early research on computational reliability

Although brief in length, this paper reveals an important issue: even seemingly reliable symbolic computation may contain systematic errors. It reminds us to exercise caution when relying on computers for mathematical research and emphasizes the importance of software verification and transparency.