You can define a topology on the positive integers by choosing as an open basis sets the series of the form an + b where a and b are relatively prime positive integers. Solomon Golumb defines this topology in [1] and proves that it is connected.
But that paper doesn’t prove that proposed basis really is a basis. That is implicitly an exercise for the reader, and we carry out that exercise here. The proof will say that certain things can be computed, and we’ll go a step further an actually compute them with Python.
Proof
To prove that these sets form the basis of a topology, we need to establish two things.
- Every point is contained in some basis element.
- The intersection of basis elements is another basis element or empty.
The first is easy. For any positive number x, the sequence (x+1)n + x contains x, and x+1 is relatively prime to x. Any other number relatively prime to x would work just as well.
The second is more interesting. Consider two sequences: an + b and cm + d. A number x in the intersection satisfies the pair of equations
x = b mod a
x = d mod c.
If a and c are relatively prime, the Chinese Remainder Theorem says that the equation has a solution y, and the solutions are unique mod ac. So the intersection of the two series is acn + y.
If a and c are not relatively prime, let r be their greatest common divisor. Then the intersection of an + b and cm + d is another sequence of the same form if b and d are congruent mod r and empty otherwise.
Separating points
A topological space is connected if it is not the union of two disjoint open sets. An easy way to make a space connected is to not have any disjoint open sets. But Golumb’s topology has plenty of disjoint open sets.
In fact, his topology is Hausdorff, meaning that any two points can be separated by disjoint open sets. The proof is simple. Take two points s and t. Let p be any prime bigger than both s and t, and consider the two sets pn + s and pn + t.
Python calculation
Our proof split into two cases: when the strides of the two series are relatively prime and when they are not.
Relatively prime strides
To get concrete, suppose we have the sequences
2, 9, 16, 23, …
and
3, 14, 25, 35, …
or in other words 7n + 2 and 11n + 3. According to the theory above, these sequences intersect because 7 and 11 are relatively prime, and the intersection should be of the form 77n + y, and we should be able to compute y from the Chinese Remainder Theorem. We will use the function crt from SymPy. (See another example of using this function here.)
>>> from sympy.ntheory.modular import crt
>>> crt([7,11], [2, 3], symmetric=False)
>>> (58, 77)
This reports that y = 58.
Now let’s verify that the intersection of our two series looks like 77n + 58.
>>> A = set(2+7*n for n in range(100))
>>> B = set(3+11*n for n in range(100))
>>> sorted(A.intersection(B))
[58, 135, 212, 289, 366, 443, 520, 597, 674]
Strides with a common factor: empty intersection
Now for the case where a and c have greatest common divisor r > 1. Consider, for example,
1, 16, 31, 46, …
and
2, 14, 26, 38, …
The sequences 15n + 1 and 12m + 2 do not intersect. The greatest common divisor of 15 and 12 is 3. Numbers in the first series are congruent to 1 mod 3 and numbers in the second series are congruent to 2 mod 3, so no number can be in both. If we didn’t realize this, we could call
crt([15,12], [1, 2], symmetric=False)
and see that it returns None.
Strides with a common factor: finding the intersection
But now let’s look at
1, 16, 31, 46, …
and
Now both sequences are congruent to 1 mod 3, so it’s at least feasible that the two series may intersect. And in fact they do.
>>> crt([15,12], [1, 13], symmetric=False)
(1, 60)
This says that the set of solutions are all congruent to 1 mod 60. Now 1 itself is not a solution, but 61 is, and so is 60n + 1 for all positive integers n. We can illustrate this as before by computing the intersection of the two series.
>>> A = set(1+15*n for n in range(30))
>>> B = set(13+12*n for n in range(30))
>>> sorted(A.intersection(B))
[61, 121, 181, 241, 301, 361]
Related posts
[1] Solomon W. Golomb. A Connected Topology for the Integers. The American Mathematical Monthly , Oct., 1959, pp. 663-665