Mathematical Arguments, Assumptions, and Counterexamples

Four relationships get blurred constantly in technical explanations. The difference between them decides what evidence would settle the question.

A necessary condition is one the conclusion cannot hold without. The implication runs conclusion ⇒ condition: differentiability implies continuity. A condition can be necessary and still be far from enough, and a counterexample is usually what exposes the gap. A sufficient condition guarantees the conclusion. The implication runs the other way, condition ⇒ conclusion — strict diagonal dominance can imply invertibility. It may be stronger than the conclusion needs, and that is exactly what makes it useful for design guarantees. An equivalent condition requires both implications, so it supports replacement in either direction: a vector is zero if and only if every coordinate is zero. That is strictly stronger than correlation.

An empirical association is none of these. Two quantities vary together in observed data — validation loss and deployment quality. That establishes no implication. It may depend on how the sample was drawn, and it can reverse under conditioning. The first three are established or destroyed by argument, and one admissible counterexample is enough to destroy them. The fourth is a measurement, and a measurement is revised by a better measurement. The ImageNet replication in the ladder section below lost two thirds of its headline effect that way. Nobody found a flaw in its logic.

Machine learning invites empirical reasoning, but mathematical claims often contain words such as “always,” “for every,” or “with probability at least.” Those words require more than a successful experiment. A proof shows why a conclusion follows from stated assumptions. A counterexample shows that a universal claim fails. A derivation manipulates expressions; a theorem also specifies the conditions under which rearranging them justifies a conclusion. The essential habit is to match the strength of the evidence to the strength of the claim.

The Mertens conjecture is what that habit is for. It states that |M(x)|/sqrt(x) < 1 for x > 1. The evidence for it is overwhelming. For 200 < x <= 10^14 the ratio stays between -0.525 and 0.571: across fourteen orders of magnitude it never gets within four tenths of the bound it is supposed to respect. Greg Hurst later computed M(x) for all x <= 10^16. Nothing in that evidence is wrong, and the conjecture is false. Odlyzko and te Riele disproved it in 1985 using LLL lattice basis reduction. Herman te Riele summarised the state of play in a 2015 survey: “In 1985, the Mertens conjecture was disproved by Odlyzko and Te Riele [23] by making use of the lattice basis reduction algorithm of Lenstra, Lenstra and Lovász [19]. The best known results today are that |M(x)|x−1/2 ≥ 1.6383 and there exists an x < exp(1.004 × 1033) for which |M(x)|x−1/2 > 1.0088.” (Exponents appear as superscripts in the original.)

There is a second lesson hiding in that disproof. It is non-constructive. No explicit counterexample is known. All that exists is an upper bound of exp(1.004 x 10^33) on the smallest x that violates the claim — a number no table will ever reach. Hurst improved the surrounding bounds to -1.837625 and 1.826054. So the tables cannot make the statement true, and the disproof cannot hand you a number to check.

Different goals require different proof strategies and different failure checks. A direct proof starts from the assumptions and derives the conclusion step by step. A proof by contrapositive proves that failure of the conclusion implies failure of an assumption. A proof by contradiction assumes the negation and derives an impossibility. A counterexample constructs one valid case that violates a universal statement. Induction establishes a base case and shows that one case implies the next.

The asymmetry between the first and the fourth has a price, and there is a computation that prints the invoice. In 2016 the Boolean Pythagorean triples problem was settled, and the whole result sits between two consecutive numbers: “Theorem 1. The set{1,..., 7824} can be partitioned into two parts, such that no part contains a Pythagorean triple, while this is impossible for {1,..., 7825}.”

Two statements, one number apart, two completely different burdens. The 7824 half is an existence claim: exhibit one partition and you are done, and anyone can check it. The 7825 half is a universal claim over every way of splitting the set in two, and no single witness can establish it. The previous best lower bound had been a partition of {1,...,7664}, found by Cooper and Overstreet. Closing the remaining gap took a cluster of 800 cores running for about 2 days. It produced a machine-checkable DRAT proof of almost 200 terabytes, compressed to a 68 gigabyte certificate. Nature reported it in 2016 under a standfirst that names the discomfort: “A computer cracks the Boolean Pythagorean triples problem — but is it really maths?” Refuting the universal statement about 7825 would have needed one partition on one line.

Proof habits are useful even when no formal theorem is written. They reveal whether a metric implication is reversible, whether a normalization preserves ordering, and whether a preprocessing rule is leakage-free. They also improve debugging. A minimal counterexample can isolate a broadcasting bug, a singular design matrix, or an unsafe threshold policy faster than a large benchmark.

The standing demonstration is Adam, because the guarantee that failed was published, cited and shipped. Three researchers at Google refuted it at ICLR in 2018, and they did not run a benchmark. They wrote down a one-dimensional problem. The feasible set is F = [-1, 1]. The convex sequence is f_t(x) = Cx when t mod 3 = 1 and -x otherwise, with C > 2, beta_1 = 0 and beta_2 = 1/(1 + C^2). On that sequence Adam converges to x = +1, and the regret-minimising point is x = -1. Their Section 3 states the consequence and then points straight at the assumption: “These examples of non-convergence contradict the claim of convergence in (Kingma & Ba, 2015), and the main issue lies in the following quantity of interest:”. The quantity is Gamma_{t+1} = sqrt(V_{t+1})/alpha_{t+1} - sqrt(V_t)/alpha_t. Kingma & Ba's 2015 proof assumed it to be positive semidefinite. For exponential-moving-average methods it can be indefinite.

That is the whole shape of the failure. Not a bug in the algorithm — an unstated condition in the proof. And it is not a corner case. Their Theorem 2 generalises the construction to any constant beta_1, beta_2 with beta_1 < sqrt(beta_2), which covers the defaults (0.9, 0.999) shipped in deep learning libraries. An independent group restated it at NeurIPS 2022: “For any beta_1, beta_2 s.t. 0 <= beta_1 < sqrt(beta_2) < 1, there exists a problem such that Adam diverges”. They noted that the commonly used (0.9, 0.999) and (0.9, 0.95) settings lie in that divergence region.

The goal is not to turn every model review into a proof seminar. It is to stop conclusions from becoming stronger than the assumptions and evidence allow.

Before accepting a theorem-like statement in an ML discussion, run this short argument audit. First, rewrite the claim: strip the jargon and state the implication in plain language. Second, mark the quantifiers — every, some, on average, asymptotically, with high probability. Third, list the assumptions: sampling, smoothness, independence, rank, numerical conditions. Fourth, search the edge cases: zeros, duplicates, singular matrices, rare events, boundary values. Fifth, try to violate the conclusion while preserving the assumptions. Sixth, decide whether the support is algebraic, probabilistic, numerical or empirical.

Steps three and four are the ones that get performed and then quietly overruled, and there is a report about what that costs. Ariane 5 was lost on its first flight on 4 June 1996. The flight was nominal to H0 + 36 seconds. Both Inertial Reference Systems were dead at about H0 + 36.7 seconds. The vehicle disintegrated at about H0 + 39 seconds. The European Space Agency quoted the inquiry board's finding in its own press release: “The failure of Ariane 501 was caused by the complete loss of guidance and attitude information 37 seconds after start of the main engine ignition sequence (30 seconds after lift-off). This loss of information was due to specification and design errors in the software of the inertial reference system.” The proximate cause was an unprotected conversion of the horizontal bias variable BH from 64-bit floating point to 16-bit signed integer.

The audit had been done. An analysis identified seven variables at risk of an Operand Error. Protection was added to four. Section 2.2 of the report explains the other three: “The reason for the three remaining variables, including the one denoting horizontal bias, being unprotected was that further reasoning indicated that they were either physically limited or that there was a large margin of safety, a reasoning which in the case of the variable BH turned out to be faulty.” The margin of safety was an assumption about the trajectory, and it was inherited: BH “was much higher than expected because the early part of the trajectory of Ariane 5 differs from that of Ariane 4”. Steps three and four had produced the right list. What failed was the unstated premise that the boundary values came from the same vehicle.

One observation can support several claims, but not all of them — and the distance between two rungs is measurable. In 2019 a team rebuilt the CIFAR-10 and ImageNet test sets by following the original collection processes, then ran the existing models against them: “We evaluate a broad range of models and find accuracy drops of 3% - 15% on CIFAR-10 and 11% - 14% on ImageNet.” Read as a counterexample, that refutes the universal claim that benchmark gains are gains in generalisation.

Then the counterexample was itself audited. A second group showed that the replication procedure introduces statistical bias. After remeasuring selection frequencies and correcting for it, “only an estimated 3.6% ± 1.5% of the original 11.7% ± 1.0% accuracy drop remains unaccounted for”. The measurement was not fabricated, and the models did lose accuracy. But roughly two thirds of the gap belonged to the instrument rather than to the claim it appeared to refute.