Comment by simonreiff | Hacker News Reader

Comment by simonreiff | Hacker News Reader

Parent Full thread

I love this topic and look forward to reading the next articles, but I suggest not saying two numbers are "equal" mod N. I would say they are "equivalent" mod N and maybe point out the broader insight: Equality is often too rigid a constraint, and we usually want to consider equivalence relations instead. We know 3 and 6 and 9 are obviously not equal, but it's useful to notice the pattern that they are all divisible evenly by 3, i.e., they are all in the equivalence class 0 mod 3.

When I think about Langlands, I think it is the power of equivalence over equality that shockingly allows us to connect the discrete world of the natural numbers (or Q) with the world of the continuous (R or C), across disparate branches of mathematics. The Modularity Theorem (every elliptic curve over Q is modular) is the foundational idea and at every step along the way, we obtain evidence of more remarkable equivalences: The conductor N of an elliptic curve versus the level N of certain congruence groups; the point count deficiency (p'th Hecke eigenvalue) of a curve and the p'th coefficient of the Fourier q-expansion; Galois reciprocity showing an equivalence between the traces of Frobenius elements acting on a cohomology, and the eigenvalues of Hecke operators; Ribet's theorem about level lowering; etc. Time and again, the theme in Langlands is that equivalence relationships make it possible for us to reason why two intricate mathematical structures that seem completely foreign are actually "essentially the same" -- not equal, but equivalent.

When saying “6 = 9 mod 3”, the “mod 3” is changing what “6” and “9” are referring to: they are now referring to the equivalence classes modulo 3 that 6 and 9 respectively belong to, and the statement expresses that those two equivalence classes are equal (hence using the equals sign is correct), are the same class. It’s a shorthand for “[6]_3 = [9]_3”, or whatever your notation is for equivalence classes.

Exactly, so [0]_3 = [3]_3 = [6]_3 = ... (and here these are indeed equalities inside Z/3Z because these are equalities of sets and not just equivalences). And for that reason, we take the "best" or canonical representative of the equivalence class to be [a]_n where 0 is less than or equal to `a`, which is always strictly less than n; hence, [0]_3 is canonical.

Actually, since the modulus is often fixed within a computation or expression, we often simply abuse notation by writing:

0 := [0]_n ("zero is defined to be the equivalence class of 0 mod n") 1 := [1]_n ...

I don't think quibbling over "equivalence" vs "equality" is useful personally. They're both "equality". Just what the sign "=" means differs depending on the type information.

E.g x: ZmodN == y: ZmodN is a different operation than x: Z == y: Z, but they're both the equality operation. We wouldn't makeup a new name for addition in this context.

It's also worth mentioning we can use the equality function (==): Z x Z -> bool to define the (==_N): ZmodN x ZmodN -> bool function in a semi-generic way. To do so, we "just" need a way to assign a unique representative (in Z) to any x: ZmodN. In other words, this is choosing a partial inverse to the reduction function modN: Z -> ZmodN. I think the partial inverse is a right inverse? so a function g : ZmodN -> Z such that (modN) o g x == x for all x in ZmodN. Anyway, given such a right inverse g, you can define (==_N): ZmodN x ZmodN -> bool via

(==_N) x y := (==) (g x) (g y)

This has the benefit that it doesn't treat ZmodN as special in any way. You can apply the same song and dance for more general quotient structures. This can be useful when doing e.g. matrix arithmetic, where you might want equivalence up to the choice of some rotation or something.

In Science I think this phenomenon is called consilience.

Reply on news.ycombinator.com