I wonder if one could use large sandpiles as a basis for a discrete log style cryptographic algorithm…

We know the max sandpile is a generator G. Then, you can do scalar multiplication nG fairly easily using something like a square-multiply technique. Is it easy to recover n? Is there a Sand Pile "Discrete Log" Problem? Elliptic curves prove extremely useful in Secure Multiparty Computations largely due to their speed and their prime orders, allowing fractions in the calculations. I wonder what properties these groups have. Are they fast? How big would they have to be? What kind of order would these groups have?

This video was like the novel Father Goriot. first half was a bit boring and took too long, and then bam! But I miss one thing. How does the substraction work? I mean, we have the zero, so if I get some sandpile A, how to compute the -A sandpile? 0-A=??

Here's something to imagine. Imagine placing a grain of sand on a three sandpile plane that follows the rules of sandpiles (apart from losing sand off the edge. If you did correctly then it will turn to a checkerbord like the below one:

I really enjoyed this; a surprising and beautiful emergence of fractals. Could you do this with each cell in the grid being a sandpile from some other set S', rather than a number, somehow? Then you could take the smaller sandpiles as a 3×1 sandpile of RGB values, and really invert an image..

Is it my imagination, or do the 'zero' sandpiles for 2×2 and 3×3 have values that are just as many as they lose to the 'edge', possibly reflecting that each box on the edge for those dimension only topples once?

i've found some interesting patterns that arise if you repeatedly enter two into each cell. there is so much here. i want to measure this and be able to explain it mathematically but i'm not at that level yet 🙁 this is amazing.

For those wondering, here are proofs of most of the claims in the video.

I am assuming that you know what an Abelian group is.

I will start off with a very important lemma. I will refer to this as the group construction lemma.

Let A be a set with a commutative associative binary operator +:A×A->A. Assume there exist elements a and b in A, and a function f:A->A, such that a+a+b=a, and such that x+f(x)=a holds for all x in A. Then for G:={a+x|x in A} and 0:=a+b we get that (G,+,0) is an Abelian group.

Proof of the group construction lemma:

First note that + is well-defined on G, as (a+x)+(a+y)=a+(x+a+y). Hence it is also commutative and associative on G. Also note that 0 is obviously an element of G. Furthermore, for all a+x in G, we have (a+x)+0=a+x+a+b=a+a+b+x=a+x, so 0 is indeed an identity of (G,+). Finally, for all a+x in G, we have (a+x)+(f(x)+b+b)=a+(x+f(x))+b+b=a+a+b+b=a+b=0, so indeed every element of G has an inverse.

I will now prove that every finite sandpile-like set M with the binary operator + defined as in the video has this property that the set S:={m+x|x in M} forms an Abelian group, where m is the maximal sandpile.

First note that + is commutative, since addition of numbers is commutative. That + is also associative is less trivial, but it comes down to the fact that the order of the toppling does not matter. So to calculate a+b+c, you can first add together the cells and then do the toppling, which makes it clear that + is associative. I can elaborate more on this if someone requests so in a reply. We will now look for a and b that satisfy the conditions of the group construction lemma. For this, define the sequence x(i)=i*m=m+m+…+m (i>0 times). Since M is finite, x can not be injective, so there exist i<j such that i*m=j*m. We find i*m+(j-i)*m=i*m, so by induction, i*m+k(j-i)*m=i*m for all k. For k>i/(j-i) we get i*m+i*m+(k(j-i)-i)*m=i*m, so for a:=i*m and b:=(k(j-i)-i)*m we get a+a+b=a. Finally, we find a function f that satisfies the condition of the group construction lemma. We take f(x)=(i-1)*m+(m-x). Here m-x just means subtracting in each cell separately. This is well-defined, because m is the maximal sandpile. It should be obvious that x+f(x)=a holds for all x in M. By the group construction lemma, we find for G:={a+x|x in M} and 0:=a+b that (G,+,0) is an Abelian group. The only thing left to show is that G=S. That S is a subset of G follows, because a+x=i*m+x=m+((i-1)*m+x). That G is a subset of S follows, because m+x=a+((m-a)+x). Again, m-a means subtracting in each cell separately.

this is the single slowest and most boring maths video i've seen. what's next? solving 2*x+1=2 in 2 hours?? stop slowing everything down so much, I want the maths not a private teacher feeding me the maths with a spoon half a bite per minute

Just wondering, so if M is the set of all 3 by 3 sandpiles…

If you have A + X = A. A is any sandpile from set S. X is any sandpile from set M (not set S). Well, X could be the zero sandpile, but it could also be the magic identity sandpile you discussed. How many things could be X?

anyone else notice that the magic sandpile for S had values in each square representing the number of grains of sand that are lost to the grid when the pile topples?

Is there any real life situation, perhaps something of the like of fundamental particles/forces interactions, 3 or more planet solar systems or some other intractable problem that these techniques can be employed to model or is this currently purely of interest only to mathematicians ?

There are so many variations which can be played with. There can be walls between adjacent cells of various heights (possibly infinite), which would change the number at which they could topple into one another – else they would have to flow around the walls. The edges can loop around (like Pac-Man/a torus/a cylinder, or as a Möbius strip, along any given axis). The toppling number can be changes (the minimum is the number of cells which count as adjacent, I think). Diagonals could count as adjacent (or only diagonals in one direction). The dimensionality can be varied (these were all two-dimensional) and the number of cells in each axis can be varied; it need not even be uniform (the edge can be jagged).

I had no idea where this was going, but that was really beautiful in the end. Well worth the long view!

I wonder if one could use large sandpiles as a basis for a discrete log style cryptographic algorithm…

We know the max sandpile is a generator G. Then, you can do scalar multiplication nG fairly easily using something like a square-multiply technique. Is it easy to recover n? Is there a Sand Pile "Discrete Log" Problem? Elliptic curves prove extremely useful in Secure Multiparty Computations largely due to their speed and their prime orders, allowing fractions in the calculations. I wonder what properties these groups have. Are they fast? How big would they have to be? What kind of order would these groups have?

@21:30 "<3"

Reminds me of simulating the wave equation on a grid

Срань господня, советский ковёр в конце. Так и знал.

notice me, sandpile!

This video was like the novel Father Goriot. first half was a bit boring and took too long, and then bam!

But I miss one thing. How does the substraction work?

I mean, we have the zero, so if I get some sandpile A, how to compute the -A sandpile? 0-A=??

'Seer-oh'

more of this guy please!

Take an infinite grid, already filled with 3 in all positions. Add one grain of sand. What happens?

1000th comment

After 15 minutes it sounds like he says senpai and not sandpile

Surely the bit at the end is a hexagonal grid not a triangular one since triangles only have 3 neighbors.

Am I the only one who thought the "2^30" grid looked like the Galactic Senate from Star Wars?

2 + 2 is 4

RAPID MATHEMATICS

3:33

Is this work published somewhere? I'm very interested in reading more about this.

Nuclear Reaction!

No, natural numbers begin with 1…the whole numbers begin with 0.

Here's something to imagine.

Imagine placing a grain of sand on a three sandpile plane that follows the rules of sandpiles (apart from losing sand off the edge. If you did correctly then it will turn to a checkerbord like the below one:

[4040404]

[0404040]

[4040404]

[0404040]

[4040404]

[0404040]

[4040404]

Try adding the all 3's to itself. It takes FOREVER to topple.

Group theory is such an underappreciated area in mathematics. Thank you for this great video!

I really enjoyed this; a surprising and beautiful emergence of fractals.

Could you do this with each cell in the grid being a sandpile from some other set S', rather than a number, somehow?

Then you could take the smaller sandpiles as a 3×1 sandpile of RGB values, and

reallyinvert an image..How about

212 000 212

101＋010＝111

212 000 212

in this case

212

101

212

is not 0

Odd how 1 = 2 = 4 work in sandpiles. Seems like broken math.

Missing context – how does this provide value to real world applications.

what's his shirt? prada? love it.

wow

Is it my imagination, or do the 'zero' sandpiles for 2×2 and 3×3 have values that are just as many as they lose to the 'edge', possibly reflecting that each box on the edge for those dimension only topples once?

What is the smallest 8-digit number possible? Make sure your answer is in base 10!

So does this mean that the set S is a group under sandpile addition?

very interesting… I would like to see a follow up video on this

One of THE best videos on Numberphile! Thanks!

So what is the identity for the infinite grid?

I would like to see the ancient mathmaticians and artists shown a computer and document their emotions.

i've found some interesting patterns that arise if you repeatedly enter two into each cell. there is so much here. i want to measure this and be able to explain it mathematically but i'm not at that level yet 🙁 this is amazing.

Where can I find a list of the zeroes for 6×6, 7×7, … grids?

wow

For those wondering, here are proofs of most of the claims in the video.

I am assuming that you know what an Abelian group is.

I will start off with a very important lemma. I will refer to this as the group construction lemma.

Let A be a set with a commutative associative binary operator +:A×A->A. Assume there exist elements a and b in A, and a function f:A->A, such that a+a+b=a, and such that x+f(x)=a holds for all x in A. Then for G:={a+x|x in A} and 0:=a+b we get that (G,+,0) is an Abelian group.

Proof of the group construction lemma:

First note that + is well-defined on G, as (a+x)+(a+y)=a+(x+a+y). Hence it is also commutative and associative on G. Also note that 0 is obviously an element of G.

Furthermore, for all a+x in G, we have (a+x)+0=a+x+a+b=a+a+b+x=a+x, so 0 is indeed an identity of (G,+).

Finally, for all a+x in G, we have (a+x)+(f(x)+b+b)=a+(x+f(x))+b+b=a+a+b+b=a+b=0, so indeed every element of G has an inverse.

I will now prove that every finite sandpile-like set M with the binary operator + defined as in the video has this property that the set S:={m+x|x in M} forms an Abelian group, where m is the maximal sandpile.

First note that + is commutative, since addition of numbers is commutative.

That + is also associative is less trivial, but it comes down to the fact that the order of the toppling does not matter. So to calculate a+b+c, you can first add together the cells and then do the toppling, which makes it clear that + is associative. I can elaborate more on this if someone requests so in a reply.

We will now look for a and b that satisfy the conditions of the group construction lemma. For this, define the sequence x(i)=i*m=m+m+…+m (i>0 times). Since M is finite, x can not be injective, so there exist i<j such that i*m=j*m. We find i*m+(j-i)*m=i*m, so by induction, i*m+k(j-i)*m=i*m for all k. For k>i/(j-i) we get i*m+i*m+(k(j-i)-i)*m=i*m, so for a:=i*m and b:=(k(j-i)-i)*m we get a+a+b=a.

Finally, we find a function f that satisfies the condition of the group construction lemma. We take f(x)=(i-1)*m+(m-x). Here m-x just means subtracting in each cell separately. This is well-defined, because m is the maximal sandpile. It should be obvious that x+f(x)=a holds for all x in M.

By the group construction lemma, we find for G:={a+x|x in M} and 0:=a+b that (G,+,0) is an Abelian group. The only thing left to show is that G=S.

That S is a subset of G follows, because a+x=i*m+x=m+((i-1)*m+x). That G is a subset of S follows, because m+x=a+((m-a)+x). Again, m-a means subtracting in each cell separately.

math is not only a language, it is art

CODING TRAIN!!

The video is super awesome but the camera blur(not focused) is kinda irritating.

What are the sequence. . 1+1/2+1/3+1/4… 1+1/2^2+1/3^2…. 1/1/2^3+1/3^3… 1/n^n upto 9… then 1-1/2^2+1/3^2…. and so many fractals.

Has anyone played the game Chain Reaction on the Android appstore??

The name should be atomic nucleus

They payoff at the end was worth watching 24 minutes for sure

Today i will show you a different type of numbers, that have this very special zero that looks like a fractal,

but…

What is a zero?*music startsdrink every time he says zero

please have luis on again some time!

but… 0 in N ?? Haven't heard anyone going by that convention, can anyone tell me which litterature has that?

Ever tried hexagonal sandpiles?

1100111 1100001 1101101 1100101 100000 1101111 1100110 100000 1101100 1101001 1100110 1100101

I learned in school that Natural numbers begin with 1(eg 1,2,3,4) and whole numbers begin with 0 ( eg 0,1,2,3,4)????

Purely awesome!!

I like the symmetry of the zeros, magic I tell you.

222 333 131

222 – 333 = 333

222 333 131

This is my favorite numberphile video

Dr. Garcia!! I loved your Discrete Mathematics class and Linear Algebra class. I can't believe you're featured on Numberphile, that's awesome!

Did I miss it? Surely if you add the identity pile to a pile of all ones, you get a different answer to all ones

Why do acid hallucinations look like math?

I wonder what this would look like if you did it on a penrose tiling.

Are there any magic square sandpiles? Cough parker square cough

this is the single slowest and most boring maths video i've seen. what's next? solving 2*x+1=2 in 2 hours?? stop slowing everything down so much, I want the maths not a private teacher feeding me the maths with a spoon half a bite per minute

Natural numbers are 1,2,3… right? Not 0,1,2,3…

Awesome to find a Mexican guy on numberphile.

19:34 this is kraftwerk

That ending is amazing. Definitely worth spending my 24 minutes watching this.

notice me, sandpile!

23:07 we can even

Z O O Mhe says 'zero' around 89 times, and 'topple'/'toppled'/'toppling' around 22.

Experienced camera operators are hard to find.

Just wondering, so if M is the set of all 3 by 3 sandpiles…

If you have A + X = A. A is any sandpile from set S. X is any sandpile from set M (not set S). Well, X could be the zero sandpile, but it could also be the magic identity sandpile you discussed. How many things could be X?

topple for 6?

That's what I'm gonna do next summer with the sand at the beach.

What do you do when you get a 5,6 or 7 ??

which BTW can happen

They r whole nubers

Se llama Luis David Garcia-Puente porque es una puente que dirige a sabiduría y conocimiento

This is some serious mindf*ck.

anyone else notice that the magic sandpile for S had values in each square representing the number of grains of sand that are lost to the grid when the pile topples?

It's sort of like a game of Pandemic.

Its a 'zero' because the values in each position is equal to the number of invalid neighbors it has

this mathematician makes better use of the brown paper than just about anyone

I love the way this guy says zero (lol).

Very underrated video

Big Bangs in the end. 🙂

Yo a heads-up

The sandpile simulator in the description doesn't function anymore.

The website loads and all the tools work but the sandpile itself never loads, making it defunct.

1,2,3… is both the counting numbers and natural numbers? Whole Numbers are 0,1,2,3… Correct?

I know a way of solving a+x=0

a=1

x=-1

1+-1=0

how do you find "-sandpile"? its obviously not "just" a substraction

Sandman wants to know your location.what about toppling a 7? Or is this possible because 3+3=6 is the highest combination made using these numbers?

Is there any real life situation, perhaps something of the like of fundamental particles/forces interactions, 3 or more planet solar systems or some other intractable problem that these techniques can be employed to model or is this currently purely of interest only to mathematicians ?

In the zero sandpile, every number is how much edges it's touching.

Fantastic!

There are so many variations which can be played with. There can be walls between adjacent cells of various heights (possibly infinite), which would change the number at which they could topple into one another – else they would have to flow around the walls. The edges can loop around (like Pac-Man/a torus/a cylinder, or as a Möbius strip, along any given axis). The toppling number can be changes (the minimum is the number of cells which count as adjacent, I think). Diagonals could count as adjacent (or only diagonals in one direction). The dimensionality can be varied (these were all two-dimensional) and the number of cells in each axis can be varied; it need not even be uniform (the edge can be jagged).

The possibilities really seem endless.

Until see this I didn't realise that I was not the only nut doing such weird number experiments. VERY INTERESTING! THANX!

did i miss where he explains how the 5 topples, where does that extra 1 go?

10:46 …we are never able to get rid of all the sand…

yeah, i know that problem for sure XD

Correct me if I'm wrong, but natural numbers don't include a zero, right? Why does he refer to natural numbers with zero in them?

I can smell the purple sharpie.

232 232 212

303+303=101

232 232 212

Anyone have a reference for the addition, zero, inverse stuff? (first part of the video)