7 ms·

A Strange Grid Reveals Hidden Connections Between Simple Numbers

163 points by headalgorithm 8y ago

CamperBob2 8y ago
Maybe I don't understand the full implications of the problem, but it seems obvious that a multiplicative table will result in more 'numerical diversity' than a summation table. Both multiplication and addition yield points on lines described by the usual mx+b equation. Addition constrains x to 1, so all of the results will be clustered near the origin, with more coincidences as an unavoidable result. Conversely, if x is allowed to exceed 1, the resulting 'lines' will spread out on the graph and leave more room for unique points. What am I missing?
- clairity 8y ago
  dunno, but it's neat to think about. multiplication can cover more ground in integer space than addition, so it can reach more unique places than addition for a given set of numbers. it's kinda like comparing how many squares knights and pawns can reach on a chessboard for a given number of moves.
  - Dylan16807 8y ago
    If you give well-spaced source numbers, they can reach the same number of spaces. 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.
- KronenR 8y ago
  Did you read the article? The numbers doesn't have to be consecutive, for example what you said is only true for arithmetic progresions, but for geometric progressions it happens the opposite that multiplications has less diversity. Read the full article.
- 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 ago
    Sure, 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 ago
      They’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 ago
        That's a good point, I'll have to stand corrected on that. Just a matter of swapping one operation for another.
        alanbernstein 8y ago
        If 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 ago
avip 8y ago
Overview of the sum/product problem by Tao https://terrytao.wordpress.com/2007/12/06/milliman-lecture-iii-sum-product-estimates-expanders-and-exponential-sums/ https://terrytao.wordpress.com/2007/12/06/milliman-lecture-i... [e: that lecture is almost a decade older than the result mentioned in OP]
csours 8y ago
It's almost like one dimension of entropy has been exhausted.
pwaai 8y ago
i dont get it...what is the hidden connection exactly?
- deleted 8y ago
  [deleted]
- zem 8y ago
  the connection is that picking your numbers so that you end up with a lot of duplicate sums constrains you to have very few duplicate products, and vice versa.
  - phkahler 8y ago
    I think it's more like having a low number of one precludes having a low number of the other. I may be wrong, but I think you can have a large nu.ber of borh.
    - AnimalMuppet 8y ago
      Like, by picking numbers that are neither an arithmetic progression nor a geometric progression.
- zwkrt 8y ago
  The real point is that no one gets the hidden connection. There are lots of tantalizing clues in number theory that lead us to believe there is some fundamental connection between addition and subtraction but we can't state it outright. This toy problem is like a black box in that we can play with it and quantify it's behavior but we don't know (exactly) why it works.
  - qubex 8y ago
    I think you mean “addition and multiplication”, not “multiplication and subtraction”... there definitely is a lot of evidence that addition and subtraction are related, but that’s just plain trivial.
sunstone 8y ago
This kind of feels like it's touching on some of the same themes as the ABC conjecture.
desc 8y ago
My intuition was already screaming 'it'll be the other way around for a geometric progression' before I read that far, but I'm damned if I can understand or even speculate why. Most likely I don't properly understand it. 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...
- metrognome 8y ago
  It's not too surprising that there are fewer unique products for a geometric progression, because subsequent terms in a geometric progression are found by multiplying by the common ratio. There will be fewer unique products when all of the numbers share that common ratio.
- thaumasiotes 8y ago
  > My intuition was already screaming 'it'll be the other way around for a geometric progression' before I read that far, but I'm damned if I can understand or even speculate why. 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)...
IshKebab 8y ago
Good job they explained what "distinct" means...
- vanderZwan 8y ago
  This is maths we are talking about, you should never assume that the common usage of words applies to the precise definition used in the maths context. Take the Boolean inclusive "or", for example.
  - IshKebab 8y ago
    I think people that know 'product', 'geometric series', etc. know what distinct means. It doesn't have some special mathematical meaning here.
    - vanderZwan 8y ago
      Sure, but this is not an article aimed at those people. Note that geometric progression is also defined later on.
qubex 8y ago
I studied applied mathematics but I have to admit number theory has always been, and probably always will be, a total mystery to me. My whole intuition is tied to dynamics and computability, and this is just absolutely alien. I’m probably more in awe of number theorists than the average person because whereas they group them with mysterious ‘mathematicians’ (with all their attendant mystique and implied genius) I’ve actually “been there, [tried] to do that” and failed, and that marks it out as an almost insurmountable peak.
deleted 8y ago
[deleted]
xiaoxiae 8y ago
I have been tree and
basicplus2 8y ago
"A long-standing puzzle seems to constrain how addition and multiplication relate to each other." The first thing to remember is that multiplication IS Addition..

163 points by headalgorithm 8y ago

Maybe I don't understand the full implications of the problem, but it seems obvious that a multiplicative table will result in more 'numerical diversity' than a summation table. Both multiplication and addition yield points on lines described by the usual mx+b equation. Addition constrains x to 1, so all of the results will be clustered near the origin, with more coincidences as an unavoidable result. Conversely, if x is allowed to exceed 1, the resulting 'lines' will spread out on the graph and leave more room for unique points. What am I missing?

clairity 8y ago
dunno, but it's neat to think about. multiplication can cover more ground in integer space than addition, so it can reach more unique places than addition for a given set of numbers. it's kinda like comparing how many squares knights and pawns can reach on a chessboard for a given number of moves.
- Dylan16807 8y ago
  If you give well-spaced source numbers, they can reach the same number of spaces. 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.
KronenR 8y ago
Did you read the article? The numbers doesn't have to be consecutive, for example what you said is only true for arithmetic progresions, but for geometric progressions it happens the opposite that multiplications has less diversity. Read the full article.
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 ago
  Sure, 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 ago
    They’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 ago
      That's a good point, I'll have to stand corrected on that. Just a matter of swapping one operation for another.
      - alanbernstein 8y ago
        If 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 ago

avip 8y ago

Overview of the sum/product problem by Tao https://terrytao.wordpress.com/2007/12/06/milliman-lecture-iii-sum-product-estimates-expanders-and-exponential-sums/ https://terrytao.wordpress.com/2007/12/06/milliman-lecture-i... [e: that lecture is almost a decade older than the result mentioned in OP]

csours 8y ago

It's almost like one dimension of entropy has been exhausted.

pwaai 8y ago

i dont get it...what is the hidden connection exactly?

deleted 8y ago
[deleted]
zem 8y ago
the connection is that picking your numbers so that you end up with a lot of duplicate sums constrains you to have very few duplicate products, and vice versa.
- phkahler 8y ago
  I think it's more like having a low number of one precludes having a low number of the other. I may be wrong, but I think you can have a large nu.ber of borh.
  - AnimalMuppet 8y ago
    Like, by picking numbers that are neither an arithmetic progression nor a geometric progression.
zwkrt 8y ago
The real point is that no one gets the hidden connection. There are lots of tantalizing clues in number theory that lead us to believe there is some fundamental connection between addition and subtraction but we can't state it outright. This toy problem is like a black box in that we can play with it and quantify it's behavior but we don't know (exactly) why it works.
- qubex 8y ago
  I think you mean “addition and multiplication”, not “multiplication and subtraction”... there definitely is a lot of evidence that addition and subtraction are related, but that’s just plain trivial.

sunstone 8y ago

This kind of feels like it's touching on some of the same themes as the ABC conjecture.

desc 8y ago

My intuition was already screaming 'it'll be the other way around for a geometric progression' before I read that far, but I'm damned if I can understand or even speculate why. Most likely I don't properly understand it. 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...

metrognome 8y ago
It's not too surprising that there are fewer unique products for a geometric progression, because subsequent terms in a geometric progression are found by multiplying by the common ratio. There will be fewer unique products when all of the numbers share that common ratio.
thaumasiotes 8y ago
> My intuition was already screaming 'it'll be the other way around for a geometric progression' before I read that far, but I'm damned if I can understand or even speculate why. 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)...

IshKebab 8y ago

Good job they explained what "distinct" means...

vanderZwan 8y ago
This is maths we are talking about, you should never assume that the common usage of words applies to the precise definition used in the maths context. Take the Boolean inclusive "or", for example.
- IshKebab 8y ago
  I think people that know 'product', 'geometric series', etc. know what distinct means. It doesn't have some special mathematical meaning here.
  - vanderZwan 8y ago
    Sure, but this is not an article aimed at those people. Note that geometric progression is also defined later on.

qubex 8y ago

I studied applied mathematics but I have to admit number theory has always been, and probably always will be, a total mystery to me. My whole intuition is tied to dynamics and computability, and this is just absolutely alien. I’m probably more in awe of number theorists than the average person because whereas they group them with mysterious ‘mathematicians’ (with all their attendant mystique and implied genius) I’ve actually “been there, [tried] to do that” and failed, and that marks it out as an almost insurmountable peak.

deleted 8y ago

[deleted]

xiaoxiae 8y ago

I have been tree and

basicplus2 8y ago

"A long-standing puzzle seems to constrain how addition and multiplication relate to each other." The first thing to remember is that multiplication IS Addition..