A Strange Grid Reveals Hidden Connections Between Simple Numbers
quantamagazine.org
quantamagazine.org
[e: that lecture is almost a decade older than the result mentioned in OP]
I'm inclined to wonder if there's a third operator which could be tested like this, such as exponentiation, but that's not commutative over integers.
Of course, if there are similarly intriguing patterns for noncommutative operators (and their sequences) the obvious next step would be to look at complex numbers and quaternions...
It's a question of forcing the number of sums/products to be low. An arithmetic progression forces a large number of identical sums for the obvious reason: (a+b) = ((a-k)+(b+k)) = ((a-2k) + (b+2k)), and so on, and those differences of k are... the definition of an arithmetic progression.
The reason a geometric progression produces a lot of identical products is exactly the same. (ab) = (a/k · bk) = (a/kk · bkk)...
What am I missing?
For products it's easy: distinct prime numbers.
For addition you can pick numbers so that each one is at least [previous number] x [number of moves] + 1. To keep it extra simple go with [number of moves + 1]^n.
So this is very easy if the number of moves is known upfront, and impossible if it's not.
And in the source puzzle the number of moves is always 2.
That isn’t true. If you pick the set of numbers {1, 2, 4, 8}, you get 10 different sums (2, 3, 4, 5, 6, 8, 9, 10, 12, and 16) but only 7 different products (1, 2, 4, 8, 16, 32, and 64)
I'm pretty sure that's not true. An arithmetic progression is x[n] = x[n-1] + k and a geometric progression is x[n] = x[n-1] * k
[1] https://en.wikipedia.org/wiki/Szemer%C3%A9di%27s_theorem
Basically, when you take integers like {1, 2, 3, 4} or {1, 3, 5, 7} (so that there are additive relations between them) (e.g. small integers), there tends to be a lot of duplicates in the addition table. But if you take integers like {1, 2, 4, 8} or {1, 3, 9, 27} (so that there are multiplicative relations between them) (e.g. very similar prime factorizations), there tend to be a lot of duplicates in the multiplication table. In other words, it's very easy to create sets with either lots of duplicates in the addition table or lots of duplicates in the multiplication table.
The conjecture is not about which kind of set is more common (so it doesn't matter even if it's true that there are a lot “more” arithmetic progressions than geometric ones, in whatever sense), but rather says there is no way you can create a set with both sorts of collisions — it's saying that if a set has many additive coincidences it can't have many multiplicative coincidences and vice-versa.
The first thing to remember is that multiplication IS Addition..
Trait A is that the numbers have a certain kind of similarity in their spacing, leading to few unique sums. Trait B is that they have a certain kind of similarity in their factors, leading to few unique products.
So from some angle it's interesting that you can't impose both types of patterns on a single set of numbers, because that inability implies a relation between two very different operations.
But on the other hand why would you assume that you should find an intersection between two restrictive algorithms? Maybe there's a hidden assumption that the algorithms would be random-ish and let you find an overlap if you search hard enough, and that assumption is screwing with people's intuition.
This is an excellent way to describe it. I had the sense that “of course the geometric sequences will collide more when multiplying” but if you asked me “why?” I would have trouble explaining. So thanks.
As far as finding a set that has an equal number of distinct sums and products, would it be possible to come up with a sequence that’s “half”-arithmetic and “half”-geometric?
I think it's key here that these two algorithms are so basic and fundamental to the structure they are executed upon (the naturals) so that every other algorithm will use them in some way. The very notion of "algorithm over the naturals" and intuition of what it means for such an algorithm to be restrictive are determined by the nature of these operations.
Put like this, it seems far less obvious to me that there is an a priori reason why the results of these two operations should or shouldn't coincide. Both scenarios seem plausible before we study problems like these.