3 ms·
”but it seems obvious that a multiplicative table will result in more 'numerical diversity' than a summation table” That isn’t true. If you pick the set of num
by Someone 8y ago
”but it seems obvious that a multiplicative table will result in more 'numerical diversity' than a summation table”
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)
- CamperBob2 8y agoSure, you can always find special-case exceptions, but I still don't see why the result is surprising in the general case. There are a lot more arithmetic progressions than geometric ones.
- empath75 8y agoThey’re both countably infinite.
- AnimalMuppet 8y ago> There are a lot more arithmetic progressions than geometric ones. 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
- CamperBob2 8y agoThat's a good point, I'll have to stand corrected on that. Just a matter of swapping one operation for another.
- alanbernstein 8y agoIf you consider all finite sequences of positive integers with all values below some limit M, it might be the case that there are more arithmetic sequences than geometric sequences. I don't think that's relevant to the article, but might be where your head was when you made that post.
- sn41 8y agoIn some deep sense, what you are saying is true : for example, if an infinite sequence of numbers is sufficiently dense, then it has arbitrarily long arithmetic progressions.[1] On the other hand, Rankin in 1990 constructed a set with positive density which does not have long geometric progressions. [1] https://en.wikipedia.org/wiki/Szemer%C3%A9di%27s_theorem https://en.wikipedia.org/wiki/Szemer%C3%A9di%27s_theorem
- svat 8y agoAh but the conjecture isn't about what happens “on average” or for a “random set” of integers. It's about what is forced to happen in every possible case. (In the “random” case there are probably very few or no duplicates anyway, as both a+b=c+d and ab=cd will be unlikely for completely random integers — note that they say d is exactly a+b-c or ab/c respectively — the conjecture is about limiting what you could possibly arrange to happen, non-randomly.) 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.