4  Computation, Representation, and Proof

4.1 Learning objectives

After completing this unit, you will be able to:

• distinguish mathematical objects, computer representations, and program output;
• explain the difference between exact arithmetic and floating-point arithmetic;
• compare floating-point numbers using stated tolerances;
• prepare an experiment record that allows the experiment to be rerun;
• write small tests of program behavior; and
• distinguish examples, counterexamples, bounded computational evidence, and general mathematical proofs.

Local prerequisites: arithmetic with rational numbers, functions, simple equations, and reasoning about “for every” versus “there exists.” No calculus or linear algebra is required.

4.2 Three layers that must not be confused

Consider the rational-number identity

$$\frac{1}{10}+\frac{2}{10}=\frac{3}{10}.$$

There are three distinct layers:

1. Mathematical objects. Rational numbers and addition are defined mathematically. The equality above is exact.
2. Representation. A computer must store objects using particular bit patterns or data structures. Not every rational number has a finite binary floating-point representation.
3. Program output. The output depends on the representation, algorithm, environment, and code that actually ran.

A common mistake is to treat the output as the object itself. A program that prints 0.30000000000000004 does not refute the rational-number identity above. It reveals a property of the floating-point representation used by the program.

4.3 Exact and floating-point arithmetic

Python provides floating-point numbers for numerical computation and Fraction for exact rational numbers.

0.1 + 0.2

Listing 4.1

0.30000000000000004

from fractions import Fraction

Fraction(1, 10) + Fraction(2, 10)

Listing 4.2

Fraction(3, 10)

Different representations serve different needs. Exact arithmetic preserves algebraic equalities, but numerators and denominators can grow in size. Floating-point arithmetic is fast and underlies many numerical libraries, but introduces rounding error.

Numerical comparisons must therefore specify both tolerance and scale:

from math import isclose

x = 0.1 + 0.2
isclose(x, 0.3, rel_tol=1e-12, abs_tol=1e-15)

Listing 4.3

True

A tolerance is not a magic formula. It is part of the experiment specification. We should be able to explain why its magnitude is appropriate for the question being asked.

4.4 A reproducible experiment contract

A computational experiment needs at least the following seven elements.

Element	Question to answer
Question	What claim or phenomenon are we investigating?
Environment	Which language and software versions are used?
Inputs	What are the data, parameters, and their units?
Method	Which algorithm and representation are used?
Checks	Which tests can detect implementation errors?
Outputs	What raw data and summaries are saved?
Conclusion	What do the results support, and what remains unproved?

Run the Unit 1 experiment from the project root:

python source/code/unit01_experiment.py

The resulting JSON file records the Python version, parameters, exact result, floating-point result, and checks of two conjectures. Running the same command in the same environment should produce identical bytes.

4.5 Proof, evidence, and counterexamples

An experiment can check that

$$n^2+n$$

is even for the first thousand integers tested. This check provides useful computational evidence: it can uncover code errors or counterexamples. However, a thousand cases do not prove the claim for every integer.

A short general proof is

$$n^2+n=n(n+1).$$

Of any two consecutive integers, one is even, so their product is even. This argument applies to every integer, not just the inputs we happened to run.

By contrast, a single counterexample is enough to refute a universal claim. The polynomial

$$p(n)=n^2+n+41$$

produces primes for many small values, but p(40)=41². A computer can find this example; the factorization explains mathematically why the claim “prime for every nonnegative integer” is false.

4.6 Tests as bounded claims

A program test makes a bounded, checkable claim, for example:

• exact rational addition produces 3/10;
• the floating-point result is close to 0.3 at the specified tolerance;
• the parity checker finds no violation in the test range;
• the experiment reports the counterexample n=40; and
• writing the JSON twice with the same environment and parameters produces identical files.

Tests increase confidence in an implementation. They do not, by themselves, prove the theorem being implemented.

4.7 Exercises

4.7.1 Exercise 1 - representation

Explain in your own words why the output 0.30000000000000004 does not make the equation $1/10+2/10=3/10$ false.

NoteHint

Separate the mathematical object from the way the computer stores it.

TipAnswer and solution

The equality is an exact equality of rational numbers. The numbers 0.1 and 0.2 are not stored exactly in the binary floating-point representation Python uses. The small error in the output comes from the approximate representation, not from a change in the rules of rational addition.

4.7.2 Exercise 2 - specifying tolerances

Describe one situation where abs_tol is appropriate and one where rel_tol is more appropriate. Give reasons, not just numbers.

NoteHint

Compare quantities close to zero with quantities that have a large natural scale.

TipAnswer and solution

For an equation residual that is theoretically zero, an absolute tolerance is appropriate because the error is compared directly with zero. When comparing two distances of roughly a million meters, a relative tolerance is more informative because the acceptable error scales with the distance. In practice, both are often used together and must be derived from the problem’s requirements.

4.7.3 Exercise 3 - the limits of an experiment

Change the parity-check limit from 1,000 to 100,000. What new conclusion is justified, and what conclusion remains unjustified?

NoteHint

More cases enlarge the region that has been checked; they do not turn it into the set of all integers.

TipAnswer and solution

Justified: no counterexample was found in the range 0 through 99,999, assuming the checker is implemented correctly. Unjustified: the claim has been proved for every integer. A general proof still requires an argument such as the factorization n(n+1).

4.7.4 Exercise 4 - a counterexample

Use the program to find the smallest nonnegative integer for which $n^2+n+41$ is composite. Then explain the result without relying on the program.

NoteHint

Check 40 and factor the result.

TipAnswer and solution

The smallest value is n=40. Exactly, $40^2+40+41=1681=41^2$, so the value is composite. This exact calculation provides a mathematical explanation of compositeness that can be checked independently of the program. Establishing that 40 is the smallest such value additionally requires exact primality checks for every integer from 0 through 39; the factorization alone does not establish minimality.

4.7.5 Exercise 5 - an experiment record

Read output/unit01-results.json. Name two fields needed to rerun the experiment and one additional piece of information that would be needed if the experiment used external libraries.

NoteHint

Look at the parameters and environment.

TipAnswer and solution

One possible answer: limit and the Python version are needed. If the experiment uses external libraries, the record must also include their names and versions, and ideally an environment file or dependency lockfile from which they can be reinstalled.

4.8 Summary

• A mathematical object is not identical to its computer representation.
• Exact and floating-point arithmetic serve different purposes.
• A tolerance is part of the specification, not a repair added after the results look bad.
• A reproducible experiment records its question, environment, inputs, method, checks, outputs, and the limits of its conclusions.
• Many examples can support a conjecture; one counterexample can refute a universal claim; a general proof requires an argument that applies throughout the domain.