#proofinatoot — Public Fediverse posts

@vnikolov @OscarCunningham @robinhouston here's the part that just does the Sierpiński triangle.

We compute four expected distances all related to points selected at random from Sierpiński triangles of side 1. The first three distances u,v,w each relate to points x,y selected from _separate_ side-1 triangles ∆ABC and ∆abc respectively, with vertices A,a identified, as if you can teleport between them with zero cost.

u is the expected distance xy if the Aa teleporter is the only route between the triangles. This is just 4/3, because the expected distance from x to A is 2/3. (That's easy to show by several methods.)

v is the expected distance xy if there's also a Bb teleporter, and w is the expected distance if B,b are linked not by a teleporter but by a walkway of length 1. We can work these out by case analysis on whether the point x is in the A, B or C subtriangle, and whether y is in the a, b or c one. In each case of both, we end up with either only one sensible route between the points (so the answer is u/2 plus a constant), or with two possibilities involving walking to _this_ pair of corners of the subtriangles or _that_ pair, with some fixed cost added to each one. If the fixed costs are the same then the answer to that case is v/2 plus a constant; if they differ by 1/2 then it's w/2 plus a constant. It turns out that it's always one of those, if it's not the case where only one route can possibly be the best. This gives us a pair of simultaneous equations in v and w, shown in the image.

Finally, s is the answer we really want: the expected distance between two points x,y in the _same_ side-1 Sierpiński triangle. With probability 2/3, the points are in different subtriangles, and the expected distance between them is w/2. And with probability 1/3, they're in the same subtriangle, so the expected distance in that case is s/2. So we have a final equation that derives s from w.

The first two simultaneous equations simplify down to
45v − 12w = 32
16w − v = 20
which give v = 188/177 and w = 233/177. And the final equation becomes
5s = 2w
which gives s = 466/885 as Oscar said.

#ProofInAToot

@vnikolov @OscarCunningham @robinhouston here's the part that just does the Sierpiński triangle.

We compute four expected distances all related to points selected at random from Sierpiński triangles of side 1. The first three distances u,v,w each relate to points x,y selected from _separate_ side-1 triangles ∆ABC and ∆abc respectively, with vertices A,a identified, as if you can teleport between them with zero cost.

u is the expected distance xy if the Aa teleporter is the only route between the triangles. This is just 4/3, because the expected distance from x to A is 2/3. (That's easy to show by several methods.)

v is the expected distance xy if there's also a Bb teleporter, and w is the expected distance if B,b are linked not by a teleporter but by a walkway of length 1. We can work these out by case analysis on whether the point x is in the A, B or C subtriangle, and whether y is in the a, b or c one. In each case of both, we end up with either only one sensible route between the points (so the answer is u/2 plus a constant), or with two possibilities involving walking to _this_ pair of corners of the subtriangles or _that_ pair, with some fixed cost added to each one. If the fixed costs are the same then the answer to that case is v/2 plus a constant; if they differ by 1/2 then it's w/2 plus a constant. It turns out that it's always one of those, if it's not the case where only one route can possibly be the best. This gives us a pair of simultaneous equations in v and w, shown in the image.

Finally, s is the answer we really want: the expected distance between two points x,y in the _same_ side-1 Sierpiński triangle. With probability 2/3, the points are in different subtriangles, and the expected distance between them is w/2. And with probability 1/3, they're in the same subtriangle, so the expected distance in that case is s/2. So we have a final equation that derives s from w.

The first two simultaneous equations simplify down to
45v − 12w = 32
16w − v = 20
which give v = 188/177 and w = 233/177. And the final equation becomes
5s = 2w
which gives s = 466/885 as Oscar said.

#ProofInAToot

@vnikolov @OscarCunningham @robinhouston here's the part that just does the Sierpiński triangle.

We compute four expected distances all related to points selected at random from Sierpiński triangles of side 1. The first three distances u,v,w each relate to points x,y selected from _separate_ side-1 triangles ∆ABC and ∆abc respectively, with vertices A,a identified, as if you can teleport between them with zero cost.

u is the expected distance xy if the Aa teleporter is the only route between the triangles. This is just 4/3, because the expected distance from x to A is 2/3. (That's easy to show by several methods.)

v is the expected distance xy if there's also a Bb teleporter, and w is the expected distance if B,b are linked not by a teleporter but by a walkway of length 1. We can work these out by case analysis on whether the point x is in the A, B or C subtriangle, and whether y is in the a, b or c one. In each case of both, we end up with either only one sensible route between the points (so the answer is u/2 plus a constant), or with two possibilities involving walking to _this_ pair of corners of the subtriangles or _that_ pair, with some fixed cost added to each one. If the fixed costs are the same then the answer to that case is v/2 plus a constant; if they differ by 1/2 then it's w/2 plus a constant. It turns out that it's always one of those, if it's not the case where only one route can possibly be the best. This gives us a pair of simultaneous equations in v and w, shown in the image.

Finally, s is the answer we really want: the expected distance between two points x,y in the _same_ side-1 Sierpiński triangle. With probability 2/3, the points are in different subtriangles, and the expected distance between them is w/2. And with probability 1/3, they're in the same subtriangle, so the expected distance in that case is s/2. So we have a final equation that derives s from w.

The first two simultaneous equations simplify down to
45v − 12w = 32
16w − v = 20
which give v = 188/177 and w = 233/177. And the final equation becomes
5s = 2w
which gives s = 466/885 as Oscar said.

#ProofInAToot

@vnikolov @OscarCunningham @robinhouston here's the part that just does the Sierpiński triangle.

We compute four expected distances all related to points selected at random from Sierpiński triangles of side 1. The first three distances u,v,w each relate to points x,y selected from _separate_ side-1 triangles ∆ABC and ∆abc respectively, with vertices A,a identified, as if you can teleport between them with zero cost.

u is the expected distance xy if the Aa teleporter is the only route between the triangles. This is just 4/3, because the expected distance from x to A is 2/3. (That's easy to show by several methods.)

v is the expected distance xy if there's also a Bb teleporter, and w is the expected distance if B,b are linked not by a teleporter but by a walkway of length 1. We can work these out by case analysis on whether the point x is in the A, B or C subtriangle, and whether y is in the a, b or c one. In each case of both, we end up with either only one sensible route between the points (so the answer is u/2 plus a constant), or with two possibilities involving walking to _this_ pair of corners of the subtriangles or _that_ pair, with some fixed cost added to each one. If the fixed costs are the same then the answer to that case is v/2 plus a constant; if they differ by 1/2 then it's w/2 plus a constant. It turns out that it's always one of those, if it's not the case where only one route can possibly be the best. This gives us a pair of simultaneous equations in v and w, shown in the image.

Finally, s is the answer we really want: the expected distance between two points x,y in the _same_ side-1 Sierpiński triangle. With probability 2/3, the points are in different subtriangles, and the expected distance between them is w/2. And with probability 1/3, they're in the same subtriangle, so the expected distance in that case is s/2. So we have a final equation that derives s from w.

The first two simultaneous equations simplify down to
45v − 12w = 32
16w − v = 20
which give v = 188/177 and w = 233/177. And the final equation becomes
5s = 2w
which gives s = 466/885 as Oscar said.

#ProofInAToot

@vnikolov @OscarCunningham @robinhouston here's the part that just does the Sierpiński triangle.

We compute four expected distances all related to points selected at random from Sierpiński triangles of side 1. The first three distances u,v,w each relate to points x,y selected from _separate_ side-1 triangles ∆ABC and ∆abc respectively, with vertices A,a identified, as if you can teleport between them with zero cost.

u is the expected distance xy if the Aa teleporter is the only route between the triangles. This is just 4/3, because the expected distance from x to A is 2/3. (That's easy to show by several methods.)

v is the expected distance xy if there's also a Bb teleporter, and w is the expected distance if B,b are linked not by a teleporter but by a walkway of length 1. We can work these out by case analysis on whether the point x is in the A, B or C subtriangle, and whether y is in the a, b or c one. In each case of both, we end up with either only one sensible route between the points (so the answer is u/2 plus a constant), or with two possibilities involving walking to _this_ pair of corners of the subtriangles or _that_ pair, with some fixed cost added to each one. If the fixed costs are the same then the answer to that case is v/2 plus a constant; if they differ by 1/2 then it's w/2 plus a constant. It turns out that it's always one of those, if it's not the case where only one route can possibly be the best. This gives us a pair of simultaneous equations in v and w, shown in the image.

Finally, s is the answer we really want: the expected distance between two points x,y in the _same_ side-1 Sierpiński triangle. With probability 2/3, the points are in different subtriangles, and the expected distance between them is w/2. And with probability 1/3, they're in the same subtriangle, so the expected distance in that case is s/2. So we have a final equation that derives s from w.

The first two simultaneous equations simplify down to
45v − 12w = 32
16w − v = 20
which give v = 188/177 and w = 233/177. And the final equation becomes
5s = 2w
which gives s = 466/885 as Oscar said.

#ProofInAToot

Does anyone know a reference for the following easy theorem about estimating area by counting lattice points?

Let \(J\) be a region of area \(a\) bounded by a Jordan curve of length \(p\). Then: \[|a - \#(\mathbb{Z}^2\cap J)| = O(p+1).\]

Proof: sweep a unit square around the boundary of \(J\); by Cavalieri's principle the area of the swept region \(B\) is \(\le 1+p\sqrt 2\). Consider the Voronoi cells of the integer lattice; outside of \(B\) they are completely inside or completely outside \(J\). Therefore, \[
\begin{align}a-1-p\sqrt 2&\le \operatorname{area}(J\setminus B)\\&\le \#(\mathbb{Z}^2\cap J)\\&\le \operatorname{area}(J\cup B)\\&\le a+1+p\sqrt 2.\end{align}\]

#ProofInAToot

Does anyone know a reference for the following easy theorem about estimating area by counting lattice points?

Let \(J\) be a region of area \(a\) bounded by a Jordan curve of length \(p\). Then: \[|a - \#(\mathbb{Z}^2\cap J)| = O(p+1).\]

Proof: sweep a unit square around the boundary of \(J\); by Cavalieri's principle the area of the swept region \(B\) is \(\le 1+p\sqrt 2\). Consider the Voronoi cells of the integer lattice; outside of \(B\) they are completely inside or completely outside \(J\). Therefore, \[
\begin{align}a-1-p\sqrt 2&\le \operatorname{area}(J\setminus B)\\&\le \#(\mathbb{Z}^2\cap J)\\&\le \operatorname{area}(J\cup B)\\&\le a+1+p\sqrt 2.\end{align}\]

#ProofInAToot

Does anyone know a reference for the following easy theorem about estimating area by counting lattice points?

Let \(J\) be a region of area \(a\) bounded by a Jordan curve of length \(p\). Then: \[|a - \#(\mathbb{Z}^2\cap J)| = O(p+1).\]

Proof: sweep a unit square around the boundary of \(J\); by Cavalieri's principle the area of the swept region \(B\) is \(\le 1+p\sqrt 2\). Consider the Voronoi cells of the integer lattice; outside of \(B\) they are completely inside or completely outside \(J\). Therefore, \[
\begin{align}a-1-p\sqrt 2&\le \operatorname{area}(J\setminus B)\\&\le \#(\mathbb{Z}^2\cap J)\\&\le \operatorname{area}(J\cup B)\\&\le a+1+p\sqrt 2.\end{align}\]

#ProofInAToot

Does anyone know a reference for the following easy theorem about estimating area by counting lattice points?

Let \(J\) be a region of area \(a\) bounded by a Jordan curve of length \(p\). Then: \[|a - \#(\mathbb{Z}^2\cap J)| = O(p+1).\]

Proof: sweep a unit square around the boundary of \(J\); by Cavalieri's principle the area of the swept region \(B\) is \(\le 1+p\sqrt 2\). Consider the Voronoi cells of the integer lattice; outside of \(B\) they are completely inside or completely outside \(J\). Therefore, \[
\begin{align}a-1-p\sqrt 2&\le \operatorname{area}(J\setminus B)\\&\le \#(\mathbb{Z}^2\cap J)\\&\le \operatorname{area}(J\cup B)\\&\le a+1+p\sqrt 2.\end{align}\]

#ProofInAToot

Does anyone know a reference for the following easy theorem about estimating area by counting lattice points?

Let \(J\) be a region of area \(a\) bounded by a Jordan curve of length \(p\). Then: \[|a - \#(\mathbb{Z}^2\cap J)| = O(p+1).\]

Proof: sweep a unit square around the boundary of \(J\); by Cavalieri's principle the area of the swept region \(B\) is \(\le 1+p\sqrt 2\). Consider the Voronoi cells of the integer lattice; outside of \(B\) they are completely inside or completely outside \(J\). Therefore, \[
\begin{align}a-1-p\sqrt 2&\le \operatorname{area}(J\setminus B)\\&\le \#(\mathbb{Z}^2\cap J)\\&\le \operatorname{area}(J\cup B)\\&\le a+1+p\sqrt 2.\end{align}\]

#ProofInAToot

We can even use this combinatorial definition to prove the divisibilty property!

We want to show that n|m implies F(n)|F(m). Suppose m = nk. Then we can consider a row of m dominoes as k blocks of n. At each of the k-1 places where these blocks meet the dominoes are either both yellow or both blue. The total number of ways to place m dominoes can be written as the sum over the 2ᵏ⁻¹ ways of colouring these boundaries of the number ways to place m dominoes compatible with that colouring. The number of ways to place the dominoes compatible with such a colouring is the product over the k blocks of the number of ways to place n dominoes compatible with the endpoints. But since we start on yellow and end on blue then there must be at least one block that likewise goes from yellow to blue. The number of ways to colour this block is F(n). So we've written F(m) as a sum of terms each of which has F(n) as a factor. ∎

#ProofInAToot

We can even use this combinatorial definition to prove the divisibilty property!

We want to show that n|m implies F(n)|F(m). Suppose m = nk. Then we can consider a row of m dominoes as k blocks of n. At each of the k-1 places where these blocks meet the dominoes are either both yellow or both blue. The total number of ways to place m dominoes can be written as the sum over the 2ᵏ⁻¹ ways of colouring these boundaries of the number ways to place m dominoes compatible with that colouring. The number of ways to place the dominoes compatible with such a colouring is the product over the k blocks of the number of ways to place n dominoes compatible with the endpoints. But since we start on yellow and end on blue then there must be at least one block that likewise goes from yellow to blue. The number of ways to colour this block is F(n). So we've written F(m) as a sum of terms each of which has F(n) as a factor. ∎

#ProofInAToot

We can even use this combinatorial definition to prove the divisibilty property!

We want to show that n|m implies F(n)|F(m). Suppose m = nk. Then we can consider a row of m dominoes as k blocks of n. At each of the k-1 places where these blocks meet the dominoes are either both yellow or both blue. The total number of ways to place m dominoes can be written as the sum over the 2ᵏ⁻¹ ways of colouring these boundaries of the number ways to place m dominoes compatible with that colouring. The number of ways to place the dominoes compatible with such a colouring is the product over the k blocks of the number of ways to place n dominoes compatible with the endpoints. But since we start on yellow and end on blue then there must be at least one block that likewise goes from yellow to blue. The number of ways to colour this block is F(n). So we've written F(m) as a sum of terms each of which has F(n) as a factor. ∎

#ProofInAToot

We can even use this combinatorial definition to prove the divisibilty property!

We want to show that n|m implies F(n)|F(m). Suppose m = nk. Then we can consider a row of m dominoes as k blocks of n. At each of the k-1 places where these blocks meet the dominoes are either both yellow or both blue. The total number of ways to place m dominoes can be written as the sum over the 2ᵏ⁻¹ ways of colouring these boundaries of the number ways to place m dominoes compatible with that colouring. The number of ways to place the dominoes compatible with such a colouring is the product over the k blocks of the number of ways to place n dominoes compatible with the endpoints. But since we start on yellow and end on blue then there must be at least one block that likewise goes from yellow to blue. The number of ways to colour this block is F(n). So we've written F(m) as a sum of terms each of which has F(n) as a factor. ∎

#ProofInAToot

We can even use this combinatorial definition to prove the divisibilty property!

We want to show that n|m implies F(n)|F(m). Suppose m = nk. Then we can consider a row of m dominoes as k blocks of n. At each of the k-1 places where these blocks meet the dominoes are either both yellow or both blue. The total number of ways to place m dominoes can be written as the sum over the 2ᵏ⁻¹ ways of colouring these boundaries of the number ways to place m dominoes compatible with that colouring. The number of ways to place the dominoes compatible with such a colouring is the product over the k blocks of the number of ways to place n dominoes compatible with the endpoints. But since we start on yellow and end on blue then there must be at least one block that likewise goes from yellow to blue. The number of ways to colour this block is F(n). So we've written F(m) as a sum of terms each of which has F(n) as a factor. ∎

#ProofInAToot

@robinhouston it does! In a trigrid-generated tiling, each ruled line would correspond to a "zone" of rhombi (a chain connected along the same direction of edge). Here I've marked all the zones I can find in your picture, coloured by direction. We seek a homeomorphism of ℝ² that turns them into unit-separation sets of lines 120° apart. But no such arrangement can permit a blue line to cross 3 red ones in between crossing 2 green ones: along one line, crossing colours alternate. #ProofInAToot

@robinhouston it does! In a trigrid-generated tiling, each ruled line would correspond to a "zone" of rhombi (a chain connected along the same direction of edge). Here I've marked all the zones I can find in your picture, coloured by direction. We seek a homeomorphism of ℝ² that turns them into unit-separation sets of lines 120° apart. But no such arrangement can permit a blue line to cross 3 red ones in between crossing 2 green ones: along one line, crossing colours alternate. #ProofInAToot

@robinhouston it does! In a trigrid-generated tiling, each ruled line would correspond to a "zone" of rhombi (a chain connected along the same direction of edge). Here I've marked all the zones I can find in your picture, coloured by direction. We seek a homeomorphism of ℝ² that turns them into unit-separation sets of lines 120° apart. But no such arrangement can permit a blue line to cross 3 red ones in between crossing 2 green ones: along one line, crossing colours alternate. #ProofInAToot

@robinhouston it does! In a trigrid-generated tiling, each ruled line would correspond to a "zone" of rhombi (a chain connected along the same direction of edge). Here I've marked all the zones I can find in your picture, coloured by direction. We seek a homeomorphism of ℝ² that turns them into unit-separation sets of lines 120° apart. But no such arrangement can permit a blue line to cross 3 red ones in between crossing 2 green ones: along one line, crossing colours alternate. #ProofInAToot

@robinhouston it does! In a trigrid-generated tiling, each ruled line would correspond to a "zone" of rhombi (a chain connected along the same direction of edge). Here I've marked all the zones I can find in your picture, coloured by direction. We seek a homeomorphism of ℝ² that turns them into unit-separation sets of lines 120° apart. But no such arrangement can permit a blue line to cross 3 red ones in between crossing 2 green ones: along one line, crossing colours alternate. #ProofInAToot

Yesterday I was working through this simple proof of what is sometimes called Cauchy's theorem, that if a prime 𝑝 divides a group 𝐺's size, then 𝐺 has an element of order 𝑝.

The idea is to build a set 𝑆 of all 𝑝-tuples from elements of 𝐺 such that each element of 𝑆 multiplies out to 1, i.e.

𝑆:={(𝑔₁,𝑔₂,…,𝑔ₚ)|∏𝑔ᵢ=1}

and then count the number of elements of 𝑆 in the following way: gather together all elements of 𝑆 that are cyclically permuted, and notice that each such class contains exactly 1 or 𝑝 elements (and all cyclic permutations of an element of 𝑆 are also in 𝑆 because if 𝑎𝑏=1 then 𝑏𝑎=1).

The classes that contain a single element correspond to an element of order 𝑝 as desired, so to show that such a class exist, observe that there is at least one such class, namely the one of (1,1,…,1), and since #𝑆=(#𝐺)ᵖ⁻¹ (every component of an element of 𝑆 is free except the last one due to the defining equation that the product equals 1), then 𝑝|#𝑆.

Thus only way that S can be decomposed into many sets of either size 1 or 𝑝 is if there is more than one set of size 1, meaning, an element of order 𝑝 exists in 𝐺.

#ProofInAToot

Yesterday I was working through this simple proof of what is sometimes called Cauchy's theorem, that if a prime 𝑝 divides a group 𝐺's size, then 𝐺 has an element of order 𝑝.

The idea is to build a set 𝑆 of all 𝑝-tuples from elements of 𝐺 such that each element of 𝑆 multiplies out to 1, i.e.

𝑆:={(𝑔₁,𝑔₂,…,𝑔ₚ)|∏𝑔ᵢ=1}

and then count the number of elements of 𝑆 in the following way: gather together all elements of 𝑆 that are cyclically permuted, and notice that each such class contains exactly 1 or 𝑝 elements (and all cyclic permutations of an element of 𝑆 are also in 𝑆 because if 𝑎𝑏=1 then 𝑏𝑎=1).

The classes that contain a single element correspond to an element of order 𝑝 as desired, so to show that such a class exist, observe that there is at least one such class, namely the one of (1,1,…,1), and since #𝑆=(#𝐺)ᵖ⁻¹ (every component of an element of 𝑆 is free except the last one due to the defining equation that the product equals 1), then 𝑝|#𝑆.

Thus only way that S can be decomposed into many sets of either size 1 or 𝑝 is if there is more than one set of size 1, meaning, an element of order 𝑝 exists in 𝐺.

#ProofInAToot

Yesterday I was working through this simple proof of what is sometimes called Cauchy's theorem, that if a prime 𝑝 divides a group 𝐺's size, then 𝐺 has an element of order 𝑝.

The idea is to build a set 𝑆 of all 𝑝-tuples from elements of 𝐺 such that each element of 𝑆 multiplies out to 1, i.e.

𝑆:={(𝑔₁,𝑔₂,…,𝑔ₚ)|∏𝑔ᵢ=1}

and then count the number of elements of 𝑆 in the following way: gather together all elements of 𝑆 that are cyclically permuted, and notice that each such class contains exactly 1 or 𝑝 elements (and all cyclic permutations of an element of 𝑆 are also in 𝑆 because if 𝑎𝑏=1 then 𝑏𝑎=1).

The classes that contain a single element correspond to an element of order 𝑝 as desired, so to show that such a class exist, observe that there is at least one such class, namely the one of (1,1,…,1), and since #𝑆=(#𝐺)ᵖ⁻¹ (every component of an element of 𝑆 is free except the last one due to the defining equation that the product equals 1), then 𝑝|#𝑆.

Thus only way that S can be decomposed into many sets of either size 1 or 𝑝 is if there is more than one set of size 1, meaning, an element of order 𝑝 exists in 𝐺.

#ProofInAToot

Yesterday I was working through this simple proof of what is sometimes called Cauchy's theorem, that if a prime 𝑝 divides a group 𝐺's size, then 𝐺 has an element of order 𝑝.

The idea is to build a set 𝑆 of all 𝑝-tuples from elements of 𝐺 such that each element of 𝑆 multiplies out to 1, i.e.

𝑆:={(𝑔₁,𝑔₂,…,𝑔ₚ)|∏𝑔ᵢ=1}

and then count the number of elements of 𝑆 in the following way: gather together all elements of 𝑆 that are cyclically permuted, and notice that each such class contains exactly 1 or 𝑝 elements (and all cyclic permutations of an element of 𝑆 are also in 𝑆 because if 𝑎𝑏=1 then 𝑏𝑎=1).

The classes that contain a single element correspond to an element of order 𝑝 as desired, so to show that such a class exist, observe that there is at least one such class, namely the one of (1,1,…,1), and since #𝑆=(#𝐺)ᵖ⁻¹ (every component of an element of 𝑆 is free except the last one due to the defining equation that the product equals 1), then 𝑝|#𝑆.

Thus only way that S can be decomposed into many sets of either size 1 or 𝑝 is if there is more than one set of size 1, meaning, an element of order 𝑝 exists in 𝐺.

#ProofInAToot

@a if you _just_ want an easy upper bound on n!, you can do better still without much more effort, by using the AM-GM inequality.

n! = Π {2,3,…,n} = GM{2,3,…,n}^{n-1} ≤ AM{2,3,…,n}^{n-1} = (n/2 + 1)^{n-1}

#ProofInAToot

(cc @11011110, though we're surely off your original topic now)

@a if you _just_ want an easy upper bound on n!, you can do better still without much more effort, by using the AM-GM inequality.

n! = Π {2,3,…,n} = GM{2,3,…,n}^{n-1} ≤ AM{2,3,…,n}^{n-1} = (n/2 + 1)^{n-1}

#ProofInAToot

(cc @11011110, though we're surely off your original topic now)

@a if you _just_ want an easy upper bound on n!, you can do better still without much more effort, by using the AM-GM inequality.

n! = Π {2,3,…,n} = GM{2,3,…,n}^{n-1} ≤ AM{2,3,…,n}^{n-1} = (n/2 + 1)^{n-1}

#ProofInAToot

(cc @11011110, though we're surely off your original topic now)

@a if you _just_ want an easy upper bound on n!, you can do better still without much more effort, by using the AM-GM inequality.

n! = Π {2,3,…,n} = GM{2,3,…,n}^{n-1} ≤ AM{2,3,…,n}^{n-1} = (n/2 + 1)^{n-1}

#ProofInAToot

(cc @11011110, though we're surely off your original topic now)

@a if you _just_ want an easy upper bound on n!, you can do better still without much more effort, by using the AM-GM inequality.

n! = Π {2,3,…,n} = GM{2,3,…,n}^{n-1} ≤ AM{2,3,…,n}^{n-1} = (n/2 + 1)^{n-1}

#ProofInAToot

(cc @11011110, though we're surely off your original topic now)

A weak ordering (https://en.wikipedia.org/wiki/Weak_ordering) is just a linear order with ties. On \(n\) items, there are obviously at least \(n!\) of them (don't use ties); here's a simple combinatorial proof that there are at most \((n+1)^{n-1}\), also proving the inequality \(n!\le(n+1)^{n-1}\). Tighter but messier upper bounds on weak orders are known.

In the complete graph \(K_{n+1}\), choose one vertex as root. By Cayley's formula (https://en.wikipedia.org/wiki/Cayley%27s_formula), it has exactly \((n+1)^{n-1}\) spanning trees. Each spanning tree can be used to weak order the non-root vertices by their distance from the root. Each weak order on non-root vertices arises from a rooted spanning tree in this way by setting the parent of each non-root vertex to be any of its immediate predecessors, or the root if it has none.

#ProofInAToot

Anyone happen to know whether this proof has been published anywhere? I know of a reference for the weaker bound \((n+1)^n\) but its proof is non-combinatorial and ugly.

A weak ordering (https://en.wikipedia.org/wiki/Weak_ordering) is just a linear order with ties. On \(n\) items, there are obviously at least \(n!\) of them (don't use ties); here's a simple combinatorial proof that there are at most \((n+1)^{n-1}\), also proving the inequality \(n!\le(n+1)^{n-1}\). Tighter but messier upper bounds on weak orders are known.

In the complete graph \(K_{n+1}\), choose one vertex as root. By Cayley's formula (https://en.wikipedia.org/wiki/Cayley%27s_formula), it has exactly \((n+1)^{n-1}\) spanning trees. Each spanning tree can be used to weak order the non-root vertices by their distance from the root. Each weak order on non-root vertices arises from a rooted spanning tree in this way by setting the parent of each non-root vertex to be any of its immediate predecessors, or the root if it has none.

#ProofInAToot

Anyone happen to know whether this proof has been published anywhere? I know of a reference for the weaker bound \((n+1)^n\) but its proof is non-combinatorial and ugly.

A weak ordering (https://en.wikipedia.org/wiki/Weak_ordering) is just a linear order with ties. On \(n\) items, there are obviously at least \(n!\) of them (don't use ties); here's a simple combinatorial proof that there are at most \((n+1)^{n-1}\), also proving the inequality \(n!\le(n+1)^{n-1}\). Tighter but messier upper bounds on weak orders are known.

In the complete graph \(K_{n+1}\), choose one vertex as root. By Cayley's formula (https://en.wikipedia.org/wiki/Cayley%27s_formula), it has exactly \((n+1)^{n-1}\) spanning trees. Each spanning tree can be used to weak order the non-root vertices by their distance from the root. Each weak order on non-root vertices arises from a rooted spanning tree in this way by setting the parent of each non-root vertex to be any of its immediate predecessors, or the root if it has none.

#ProofInAToot

Anyone happen to know whether this proof has been published anywhere? I know of a reference for the weaker bound \((n+1)^n\) but its proof is non-combinatorial and ugly.

A weak ordering (https://en.wikipedia.org/wiki/Weak_ordering) is just a linear order with ties. On \(n\) items, there are obviously at least \(n!\) of them (don't use ties); here's a simple combinatorial proof that there are at most \((n+1)^{n-1}\), also proving the inequality \(n!\le(n+1)^{n-1}\). Tighter but messier upper bounds on weak orders are known.

In the complete graph \(K_{n+1}\), choose one vertex as root. By Cayley's formula (https://en.wikipedia.org/wiki/Cayley%27s_formula), it has exactly \((n+1)^{n-1}\) spanning trees. Each spanning tree can be used to weak order the non-root vertices by their distance from the root. Each weak order on non-root vertices arises from a rooted spanning tree in this way by setting the parent of each non-root vertex to be any of its immediate predecessors, or the root if it has none.

#ProofInAToot

Anyone happen to know whether this proof has been published anywhere? I know of a reference for the weaker bound \((n+1)^n\) but its proof is non-combinatorial and ugly.

A weak ordering (https://en.wikipedia.org/wiki/Weak_ordering) is just a linear order with ties. On \(n\) items, there are obviously at least \(n!\) of them (don't use ties); here's a simple combinatorial proof that there are at most \((n+1)^{n-1}\), also proving the inequality \(n!\le(n+1)^{n-1}\). Tighter but messier upper bounds on weak orders are known.

In the complete graph \(K_{n+1}\), choose one vertex as root. By Cayley's formula (https://en.wikipedia.org/wiki/Cayley%27s_formula), it has exactly \((n+1)^{n-1}\) spanning trees. Each spanning tree can be used to weak order the non-root vertices by their distance from the root. Each weak order on non-root vertices arises from a rooted spanning tree in this way by setting the parent of each non-root vertex to be any of its immediate predecessors, or the root if it has none.

#ProofInAToot

Anyone happen to know whether this proof has been published anywhere? I know of a reference for the weaker bound \((n+1)^n\) but its proof is non-combinatorial and ugly.

Four kissing circles' centers spread
as sums of inverse bends;
squared distance into square array
now Cayley-Menger sends.[†]
The volume of their convex hull,
as Bradford[*] saw, must equal null,
And calculating matrix norms,
The simplified result then forms:
The sum of the squares of all four bends
Is half the square of their sum!

[†] https://en.wikipedia.org/wiki/Cayley%E2%80%93Menger_determinant

[*] Bradford, Alden (2023), "An even more straightforward proof of Descartes's circle theorem", The Mathematical Intelligencer, 45 (3): 263–265, https://doi.org/10.1007/s00283-022-10234-6

#ProofInAToot

Four kissing circles' centers spread
as sums of inverse bends;
squared distance into square array
now Cayley-Menger sends.[†]
The volume of their convex hull,
as Bradford[*] saw, must equal null,
And calculating matrix norms,
The simplified result then forms:
The sum of the squares of all four bends
Is half the square of their sum!

[†] https://en.wikipedia.org/wiki/Cayley%E2%80%93Menger_determinant

[*] Bradford, Alden (2023), "An even more straightforward proof of Descartes's circle theorem", The Mathematical Intelligencer, 45 (3): 263–265, https://doi.org/10.1007/s00283-022-10234-6

#ProofInAToot

Four kissing circles' centers spread
as sums of inverse bends;
squared distance into square array
now Cayley-Menger sends.[†]
The volume of their convex hull,
as Bradford[*] saw, must equal null,
And calculating matrix norms,
The simplified result then forms:
The sum of the squares of all four bends
Is half the square of their sum!

[†] https://en.wikipedia.org/wiki/Cayley%E2%80%93Menger_determinant

[*] Bradford, Alden (2023), "An even more straightforward proof of Descartes's circle theorem", The Mathematical Intelligencer, 45 (3): 263–265, https://doi.org/10.1007/s00283-022-10234-6

#ProofInAToot

Four kissing circles' centers spread
as sums of inverse bends;
squared distance into square array
now Cayley-Menger sends.[†]
The volume of their convex hull,
as Bradford[*] saw, must equal null,
And calculating matrix norms,
The simplified result then forms:
The sum of the squares of all four bends
Is half the square of their sum!

[†] https://en.wikipedia.org/wiki/Cayley%E2%80%93Menger_determinant

[*] Bradford, Alden (2023), "An even more straightforward proof of Descartes's circle theorem", The Mathematical Intelligencer, 45 (3): 263–265, https://doi.org/10.1007/s00283-022-10234-6

#ProofInAToot

Four kissing circles' centers spread
as sums of inverse bends;
squared distance into square array
now Cayley-Menger sends.[†]
The volume of their convex hull,
as Bradford[*] saw, must equal null,
And calculating matrix norms,
The simplified result then forms:
The sum of the squares of all four bends
Is half the square of their sum!

[†] https://en.wikipedia.org/wiki/Cayley%E2%80%93Menger_determinant

[*] Bradford, Alden (2023), "An even more straightforward proof of Descartes's circle theorem", The Mathematical Intelligencer, 45 (3): 263–265, https://doi.org/10.1007/s00283-022-10234-6

#ProofInAToot

@simontatham This doesn't quite scan:

The square root of 2 is irrational
Say teachers both local and national
If it's v over u,
Square and count powers of two,
They're different but can't be so dash it all!

#ProofInALimerick #ProofInAToot

@simontatham This doesn't quite scan:

The square root of 2 is irrational
Say teachers both local and national
If it's v over u,
Square and count powers of two,
They're different but can't be so dash it all!

#ProofInALimerick #ProofInAToot

@simontatham This doesn't quite scan:

The square root of 2 is irrational
Say teachers both local and national
If it's v over u,
Square and count powers of two,
They're different but can't be so dash it all!

#ProofInALimerick #ProofInAToot

@simontatham This doesn't quite scan:

The square root of 2 is irrational
Say teachers both local and national
If it's v over u,
Square and count powers of two,
They're different but can't be so dash it all!

#ProofInALimerick #ProofInAToot

@simontatham This doesn't quite scan:

The square root of 2 is irrational
Say teachers both local and national
If it's v over u,
Square and count powers of two,
They're different but can't be so dash it all!

#ProofInALimerick #ProofInAToot

@domotorp Well, it's an induction proof at the level of an undergraduate exercise. I don't think that's quite easy enough to call it "trivial". Maybe it looks trivial to you because you have already internalized this concept to the point where you don't notice when you are using it?

Here is the proof I know. Maybe you can find a simpler argument that persuades me that it really is trivial.

Claim: For a monotone availability condition on a finite set of elements, each two sequences of elements chosen greedily according to the condition until no more elements are available have equal sets of elements.

Proof: Induction on the lengths of the suffixes of the sequences starting from where they first differ. Base case: if one sequence has an empty suffix, the other suffix must also be empty, because otherwise its next element would be available to the first sequence. Inductive case: the next symbol in the first sequence is also available in the second sequence so it must appear somewhere. Reorder the second sequence by pulling this element forward to the same position it has in the first sequence. The reordered sequence has the same elements as the second sequence and is still valid by monotonicity of the availability condition for the other elements. By the induction hypothesis, it also has the same elements as the first sequence.

#ProofInAToot

@domotorp Well, it's an induction proof at the level of an undergraduate exercise. I don't think that's quite easy enough to call it "trivial". Maybe it looks trivial to you because you have already internalized this concept to the point where you don't notice when you are using it?

Here is the proof I know. Maybe you can find a simpler argument that persuades me that it really is trivial.

Claim: For a monotone availability condition on a finite set of elements, each two sequences of elements chosen greedily according to the condition until no more elements are available have equal sets of elements.

Proof: Induction on the lengths of the suffixes of the sequences starting from where they first differ. Base case: if one sequence has an empty suffix, the other suffix must also be empty, because otherwise its next element would be available to the first sequence. Inductive case: the next symbol in the first sequence is also available in the second sequence so it must appear somewhere. Reorder the second sequence by pulling this element forward to the same position it has in the first sequence. The reordered sequence has the same elements as the second sequence and is still valid by monotonicity of the availability condition for the other elements. By the induction hypothesis, it also has the same elements as the first sequence.

#ProofInAToot

@domotorp Well, it's an induction proof at the level of an undergraduate exercise. I don't think that's quite easy enough to call it "trivial". Maybe it looks trivial to you because you have already internalized this concept to the point where you don't notice when you are using it?

Here is the proof I know. Maybe you can find a simpler argument that persuades me that it really is trivial.

Claim: For a monotone availability condition on a finite set of elements, each two sequences of elements chosen greedily according to the condition until no more elements are available have equal sets of elements.

Proof: Induction on the lengths of the suffixes of the sequences starting from where they first differ. Base case: if one sequence has an empty suffix, the other suffix must also be empty, because otherwise its next element would be available to the first sequence. Inductive case: the next symbol in the first sequence is also available in the second sequence so it must appear somewhere. Reorder the second sequence by pulling this element forward to the same position it has in the first sequence. The reordered sequence has the same elements as the second sequence and is still valid by monotonicity of the availability condition for the other elements. By the induction hypothesis, it also has the same elements as the first sequence.

#ProofInAToot

@domotorp Well, it's an induction proof at the level of an undergraduate exercise. I don't think that's quite easy enough to call it "trivial". Maybe it looks trivial to you because you have already internalized this concept to the point where you don't notice when you are using it?

Here is the proof I know. Maybe you can find a simpler argument that persuades me that it really is trivial.

Claim: For a monotone availability condition on a finite set of elements, each two sequences of elements chosen greedily according to the condition until no more elements are available have equal sets of elements.

Proof: Induction on the lengths of the suffixes of the sequences starting from where they first differ. Base case: if one sequence has an empty suffix, the other suffix must also be empty, because otherwise its next element would be available to the first sequence. Inductive case: the next symbol in the first sequence is also available in the second sequence so it must appear somewhere. Reorder the second sequence by pulling this element forward to the same position it has in the first sequence. The reordered sequence has the same elements as the second sequence and is still valid by monotonicity of the availability condition for the other elements. By the induction hypothesis, it also has the same elements as the first sequence.

#ProofInAToot

@domotorp Well, it's an induction proof at the level of an undergraduate exercise. I don't think that's quite easy enough to call it "trivial". Maybe it looks trivial to you because you have already internalized this concept to the point where you don't notice when you are using it?

Here is the proof I know. Maybe you can find a simpler argument that persuades me that it really is trivial.

Claim: For a monotone availability condition on a finite set of elements, each two sequences of elements chosen greedily according to the condition until no more elements are available have equal sets of elements.

Proof: Induction on the lengths of the suffixes of the sequences starting from where they first differ. Base case: if one sequence has an empty suffix, the other suffix must also be empty, because otherwise its next element would be available to the first sequence. Inductive case: the next symbol in the first sequence is also available in the second sequence so it must appear somewhere. Reorder the second sequence by pulling this element forward to the same position it has in the first sequence. The reordered sequence has the same elements as the second sequence and is still valid by monotonicity of the availability condition for the other elements. By the induction hypothesis, it also has the same elements as the first sequence.

#ProofInAToot

I'm curious, has anyone seen this one before:

Lemma: Suppose that three given points in \(\mathbb{R}^d\) are disjoint from an open convex set \(U\). Then two of the points can be connected by a curve disjoint from \(U\) of length at most twice their Euclidean distance.

For instance, in the plane, two nearby points can be separated by a thickened line or line segment, so they have no short connecting curve, but three points cannot all be made far from each other by a single convex obstacle.

Proof: Consider the plane containing the three points; if \(U\) does not intersect this plane then the points can be connected directly. Within this plane draw a line through each point, disjoint from \(U\). If the three lines form a triangle or unbounded three-sided region containing \(U\), with the three points on its sides, then one of its internal angles is at least \(60^\circ\), and the curve connecting two points through this angle has length at most twice the distance between the points (worst case: \(U\) is an equilateral triangle and the three points are its edge midpoints). If one of the three points is not on a side of the region containing \(U\), it can see the entire line through another of the points, and be connected directly to that point.

#ProofInAToot

I'm curious, has anyone seen this one before:

Lemma: Suppose that three given points in \(\mathbb{R}^d\) are disjoint from an open convex set \(U\). Then two of the points can be connected by a curve disjoint from \(U\) of length at most twice their Euclidean distance.

For instance, in the plane, two nearby points can be separated by a thickened line or line segment, so they have no short connecting curve, but three points cannot all be made far from each other by a single convex obstacle.

Proof: Consider the plane containing the three points; if \(U\) does not intersect this plane then the points can be connected directly. Within this plane draw a line through each point, disjoint from \(U\). If the three lines form a triangle or unbounded three-sided region containing \(U\), with the three points on its sides, then one of its internal angles is at least \(60^\circ\), and the curve connecting two points through this angle has length at most twice the distance between the points (worst case: \(U\) is an equilateral triangle and the three points are its edge midpoints). If one of the three points is not on a side of the region containing \(U\), it can see the entire line through another of the points, and be connected directly to that point.

#ProofInAToot

I'm curious, has anyone seen this one before:

Lemma: Suppose that three given points in \(\mathbb{R}^d\) are disjoint from an open convex set \(U\). Then two of the points can be connected by a curve disjoint from \(U\) of length at most twice their Euclidean distance.

For instance, in the plane, two nearby points can be separated by a thickened line or line segment, so they have no short connecting curve, but three points cannot all be made far from each other by a single convex obstacle.

Proof: Consider the plane containing the three points; if \(U\) does not intersect this plane then the points can be connected directly. Within this plane draw a line through each point, disjoint from \(U\). If the three lines form a triangle or unbounded three-sided region containing \(U\), with the three points on its sides, then one of its internal angles is at least \(60^\circ\), and the curve connecting two points through this angle has length at most twice the distance between the points (worst case: \(U\) is an equilateral triangle and the three points are its edge midpoints). If one of the three points is not on a side of the region containing \(U\), it can see the entire line through another of the points, and be connected directly to that point.

#ProofInAToot

I'm curious, has anyone seen this one before:

Lemma: Suppose that three given points in \(\mathbb{R}^d\) are disjoint from an open convex set \(U\). Then two of the points can be connected by a curve disjoint from \(U\) of length at most twice their Euclidean distance.

For instance, in the plane, two nearby points can be separated by a thickened line or line segment, so they have no short connecting curve, but three points cannot all be made far from each other by a single convex obstacle.

Proof: Consider the plane containing the three points; if \(U\) does not intersect this plane then the points can be connected directly. Within this plane draw a line through each point, disjoint from \(U\). If the three lines form a triangle or unbounded three-sided region containing \(U\), with the three points on its sides, then one of its internal angles is at least \(60^\circ\), and the curve connecting two points through this angle has length at most twice the distance between the points (worst case: \(U\) is an equilateral triangle and the three points are its edge midpoints). If one of the three points is not on a side of the region containing \(U\), it can see the entire line through another of the points, and be connected directly to that point.

#ProofInAToot

I'm curious, has anyone seen this one before:

Lemma: Suppose that three given points in \(\mathbb{R}^d\) are disjoint from an open convex set \(U\). Then two of the points can be connected by a curve disjoint from \(U\) of length at most twice their Euclidean distance.

For instance, in the plane, two nearby points can be separated by a thickened line or line segment, so they have no short connecting curve, but three points cannot all be made far from each other by a single convex obstacle.

Proof: Consider the plane containing the three points; if \(U\) does not intersect this plane then the points can be connected directly. Within this plane draw a line through each point, disjoint from \(U\). If the three lines form a triangle or unbounded three-sided region containing \(U\), with the three points on its sides, then one of its internal angles is at least \(60^\circ\), and the curve connecting two points through this angle has length at most twice the distance between the points (worst case: \(U\) is an equilateral triangle and the three points are its edge midpoints). If one of the three points is not on a side of the region containing \(U\), it can see the entire line through another of the points, and be connected directly to that point.

#ProofInAToot

@Scmbradley #ProofInAToot!

@Scmbradley #ProofInAToot!

@Scmbradley #ProofInAToot!

@Scmbradley #ProofInAToot!

@Scmbradley #ProofInAToot!

Let \(\newcommand{\vrp}{\varepsilon}\vrp_{AJ},\vrp_{JK},\vrp_{AK}\) be pairwise timelike events in a flat region, and event \(\vrp_{AP}\) timelike and straight wrt. \(\vrp_{AJ},\vrp_{AK}\) and lightlike wrt. \(\vrp_{JK}\). Consequently, these four events are plane wrt. each other:
\[\newcommand{\sqv}{\scriptsize s^2[\vrp} 0=\begin{vmatrix}0\!&1&1&1&1\\1\!&0&\sqv_{AJ},\vrp_{AP}]&\sqv_{AJ},\vrp_{AK}]&\sqv_{AJ},\vrp_{JK}]\\1\!&\!\!\sqv_{AJ},\vrp_{AP}]\!\!&0&\!\!(\sqrt{\sqv_{AJ},\vrp_{AK}]}\!-\!\!\sqrt{\sqv_{AJ},\vrp_{AP}]})^2\!\!&0\\1\!&\!\!\sqv_{AJ},\vrp_{AK}]\!\!&\!\!(\sqrt{\sqv_{AJ},\vrp_{AK}]}\!-\!\!\sqrt{\sqv_{AJ},\vrp_{AP}]})^2\!\!&0&\sqv_{JK},\vrp_{AK}]\\1\!&\!\!\sqv_{AJ},\vrp_{JK}]\!\!&0&\sqv_{JK},\vrp_{AK}]&0\end{vmatrix}.\]
Thus:\[\frac{\sqv_{AJ},\vrp_{JK}]}{\sqv_{AJ},\vrp_{AK}]}=1-\sqrt{\frac{\sqv_{AJ},\vrp_{AP}]}{\sqv_{AJ},\vrp_{AK}]}}+\frac{\sqv_{JK},\vrp_{AK}]}{\sqv_{AJ},\vrp_{AK}]}\left(\!1\!-\!\sqrt{\frac{\sqv_{AJ},\vrp_{AK}]}{\sqv_{AJ},\vrp_{AP}]}}\right).\]

Now adding the following inequality:
\[2\sqrt{\frac{\sqv_{JK},\vrp_{AK}]}{\sqv_{AJ},\vrp_{AK}]}}\le\frac{\sqv_{JK},\vrp_{AK}]}{\sqv_{AJ},\vrp_{AK}]}\sqrt{\frac{\sqv_{AJ},\vrp_{AK}]}{\sqv_{AJ},\vrp_{AJ}]}}+\sqrt{\frac{\sqv_{AJ},\vrp_{AP}]}{\sqv_{AJ},\vrp_{AK}]}}\]

and collecting yields:
\[\frac{\sqv_{AJ},\vrp_{JK}]}{\sqv_{AJ},\vrp_{AK}]}+2\sqrt{\frac{\sqv_{JK},\vrp_{AK}]}{\sqv_{AJ},\vrp_{AK}]}}\le1+\frac{\sqv_{JK},\vrp_{AK}]}{\sqv_{AJ},\vrp_{AK}]},\]

Therefore
\[
\sqrt{\frac{\sqv_{AJ},\vrp_{JK}]}{\sqv_{AJ},\vrp_{AK}]}}+\sqrt{\frac{\sqv_{JK},\vrp_{AK}]}{\sqv_{AJ},\vrp_{AK}]}}\le1,\]

a.k.a. reverse triangle inequality of (timelike) Lorentzian distances, https://en.wikipedia.org/wiki/Triangle_inequality#Reversal_in_Minkowski_space

#ProofInAToot #TwinFauxParadox #Relativity #Spacetime