Topic by FractalFusion

Posted: 10/20/2018 11:41 PM

Quote

FractalFusion

Editor, Skilled player (1939)

Joined: 6/15/2005
Posts: 3247

I figured out the trick behind this week's Riddler Classic. I'll leave the problem here in case you want to do it yourself. The problem is stated below: Note: The links below are my doing. The problem can be reworded as a graph theory problem. The archipelago can be thought of as a tree, where we remove vertices independently with probability p and count the remaining connected components. ---- You live on the volcanic archipelago of Riddleria. The Riddlerian Islands are a 30-minute boat ride off the shores of the nearby mainland. Your archipelago is connected via a network of bridges, forming one unified community. In an effort to conserve resources, the ancient Riddlerians who built this network opted not to build bridges between any two islands that were already connected to the community otherwise. Hence, there is exactly one path from any one island to any other island. One day, you feel the ground start to rumble — the islands’ volcanoes are stirring. You’re not sure whether any volcano is going to blow, but you and the rest of the Riddlerians flee the archipelago in rowboats bound for the mainland just to be safe. But as you leave, you look back and wonder what will become of your home. Each island contains exactly one volcano. You know that if a volcano erupts, the subterranean pressure change will be so great that the volcano will collapse in on itself, causing its island — and any connected bridges — to crumble into the ocean. Remarkably, other islands will be spared unless their own volcanoes erupt. But if enough bridges go down, your once-unified archipelagic community could split into several smaller, disjointed communities. If there were N islands in the archipelago originally and each volcano erupts independently with probability p, how many disjointed communities can you expect to find when you return? What value of p maximizes this number? ---- Even though it looks difficult (and Riddler is known for similar-looking problems that require computer-assisted computation), there is a trick that greatly simplifies the problem. The problem is doable on paper and no computers are required.

Tub wrote:

http://mathworld.wolfram.com/GoatProblem.html http://oeis.org/A133731 Wikipedia page

How was such a mundane problem deemed worthy of Wikipedia/Wolfram/OEIS pages? This is just one of many field-grazing problems. Can there be Wikipedia pages for all the problems I came up with? :D

Posted: 10/21/2018 6:22 AM

Quote

Warp

Banned User, Former player

Joined: 3/10/2004
Posts: 7698
Location: Finland

FractalFusion wrote:

How was such a mundane problem deemed worthy of Wikipedia/Wolfram/OEIS pages?

Numberphile had an episode where the host is asked two random numbers, and a sequence is created from them by adding two consecutive numbers in the series (to demonstrate that their ratio approaches phi). An off-hand joke is made that it will be soon appear in OEIS. And sure enough: http://oeis.org/A247698

Posted: 10/21/2018 6:06 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

For Riddler Classic, consider that you have a tree of N vertices, and that you know the expected value E[N,p] of the number of connected components for N islands that collapse with probability p. Now, make a tree of N+1 vertices by adding a leaf node. What's the expected value now? If the new leaf node collapses, then the expected number of components is the same as the N vertex tree. If it doesn't collapse, then there are two possibilities. If the node you attached the leaf to survives, then the number of components stays the same. If it doesn't, then the number rises by 1. Since the node collapses with probability p, the expected value will rise by p when the leaf survives. Therefore: E[N+1,p] = p*E[N,p] + (1-p)*(E[N,p]+p) Since it's possible to construct any tree by starting with a single vertex and keep adding leaf nodes, the previous equation says the expected value depends only on the number of vertices, not on the tree's topology. In particular, we can calculate it for the star shaped tree, where we have N-1 vertices connected to a central one. Now, if the center doesn't collapse, we always have 1 component. If it does, then we have N-1 independent expected values of 1-p. Calculating, we have E[N,p] = (1-p+Np)(1-p) And you can verify it satisfies the other equation as a sanity check. If N=1, it's maximized for p=0. For other N, expand and derive with respect to p, equate to 0 and find p = N-2/(2N-2) , which is always a well defined probability, since N >= 2 implies p >= 0 and 2N > N implies p < 1. EDIT: It seems I missed an easier way to calculate E[N,p]. The first formula is just E[N+1,p] = E[N,p] + p(1-p) Using the fact that E[1,p]=1-p, the expression for E[N,p] follows immediately. Curiously, since you guys are mentioning OEIS, it seems this problem deduces a stronger result than what's known there. By plugging p=1/2 and multiplying by 2^N , we get the total sum of connected components formed by all vertex subsets of a tree of N vertices. That gives A(n) = (n+1)*2^(n-2) The first numbers are 1, 3, 8, 20, 48 This is https://oeis.org/A001792 It's written there: a(n) is the number of runs of consecutive 1's in all binary sequences of length (n+1). - Geoffrey Critzer, Jul 02 2009 It turns out this is a direct corollary of the previous result. Binary sequences represent whether a vertex is included in a subset or not (0 if it's out, 1 if it's in). A run of consecutive 1's is simply a connected component of a tree with the topology of a line: 1-2-3-...-n So, someone should probably publish a paper so that we can strengthen the result at OEIS (or perhaps the guys at Riddler have already done it, I know it's common practice to make exercises based on elementary results that you derived on research papers :P)

Posted: 10/23/2018 12:52 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

Show that the following code is correct:

Language: cpp
bool isEven(int x) {
  while (true) {
    if (x == 0) return true;
    else if (x == 1) return false;
    else x = x*x;
  }
}

Posted: 10/23/2018 3:03 PM

Quote

OmnipotentEntity

He/Him

Player (36)

Joined: 9/11/2004
Posts: 2623

Any n-bit number that ends with a 0 is even, whether it is positive or negative. If it ends with a 1 it is odd. Let us say for the sake of argument that we're dealing with 8 bit signed integers. Our two cases are: XXXXXXX0 * XXXXXXX0 and XXXXXXX1 * XXXXXXX1 Multiplying each of these through we get: XXXXXX00 for the even side. And the 0s tend to accumulate. For the odd side it's a bit more complicated. In the 1s digit we're left with a 1, obviously (odd * odd = odd); however, in the 2s digit we have the old 2s digit + old 2s digit. Because 0 + 0 = 0 and 1 + 1 = 0b10, this means that a 0 will live in the 2s place after multiplication. XXXXXX01 On the next iteration another zero appears in the new 4s place because it is equal to the 0b10*current 4s. The twos digit does not change because it is equal to 1 * 0 + 0 * 1. So we get an additional 0 XXXXX001 And so on. Eventually the zeros will pile up until it shifts them out of the precision of the integer regardless of how many bits it is.

Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.

Posted: 10/23/2018 6:19 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

Very nice! I did not know about this analysis of the bits. There's a more standard solution using modular arithmetic. It's straightforward to see that by repeatedly squaring a number, an odd number will never overflow to 0 and an even one will never overflow to 1. Since integers overflow, all our computations are in fact modular arithmetic with a modulus of 2³². Suppose a given number x is even. Then, gcd(x,2³²) >= 2. That means x is not in the multiplicative group of 2³². In particular, we have x=2k for a given integer k. After five squarings, we have x³²=2³²k³². This number is a multiple of 2³² and thus, overflows to 0. Now, suppose x is odd. Then, gcd(x,2³²)=1 and x is in the multiplicative group of 2³². Therefore, Euler's theorem says x^phi(2³²) = 1. But phi(2³²)=2³¹, see here. That means that, after at most 31 squarings, x will overflow to 1, and that finishes the proof.

Posted: 10/24/2018 12:27 AM

Quote

FractalFusion

Editor, Skilled player (1939)

Joined: 6/15/2005
Posts: 3247

Looks like p4wn3r found the trick to Riddler Classic. The surprising result is that the expected number of communities formed depends only on the number of islands N and not on how they are connected. Here's how I did it below: The expectation for N=1 is clearly 1-p (probability of surviving), and each additional island adds p(1-p) to the expectation regardless of which other island it is connected to (to add 1 to the community count, the newly added island must survive and the island it is joined to must be destroyed). This gives E(N,p) = 1-p + p(1-p)(N-1). For N=1, it is maximized at p=0, and the expectation in this case is 1. For N>1, E(N,p) can be written as

(image generated from latex2png.com) So the maximum occurs at p=(N-2)/(2(N-1)) and the maximum expectation is N^2/(4(N-1)). Example values for N, p which gives max expectation, and max expectation: N=1: p=0, E(N,p)=1 N=2: p=0, E(N,p)=1 N=3: p=1/4, E(N,p)=9/8 N=4: p=1/3, E(N,p)=4/3 N=5: p=3/8, E(N,p)=25/16 N=6: p=2/5, E(N,p)=9/5 N=7: p=5/12, E(N,p)=49/24 Note that as N goes to infinity, the p at which the max expectation occurs approaches 1/2 and the corresponding expected number of communities is approximately (N+1)/4.

Posted: 10/29/2018 9:35 AM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

From the triangle determined by points A, B, C the three altitudes are drawn, intersecting the opposite side at points D, E and F, and the triangle's circumscribed circle at D', E' and F'. Express the lengths of AD, BE, CF, AD', BE', CF' in terms of the triangle's angles and the circumscribed radius R.

Posted: 10/31/2018 5:37 AM

Quote

FractalFusion

Editor, Skilled player (1939)

Joined: 6/15/2005
Posts: 3247

p4wn3r wrote:

From the triangle determined by points A, B, C the three altitudes are drawn, intersecting the opposite side at points D, E and F, and the triangle's circumscribed circle at D', E' and F'. Express the lengths of AD, BE, CF, AD', BE', CF' in terms of the triangle's angles and the circumscribed radius R.

Here A,B,C,D,E,F,D',E',F' are all the points specified in the problem. O is the circumcenter, the red circle is the circumcircle, R is the circumradius (R=|OA|=|OB|=|OC|), and the green lines are the heights of the triangle extended to the circumcircle. We use the following notation: A=∠CAB, B=∠ABC, C=∠BCA, a=|BC|, b=|AC|, c=|AB| From the diagram above, we have ∠COB=2A since an angle at the center is twice the angle at the circumference subtending the same arc/chord. By cosine law: a = sqrt(R^2+R^2-2R^2cos(∠COB)) = R*sqrt(2-2cos(2A)) Likewise: b=R*sqrt(2-2cos(2B)) c=R*sqrt(2-2cos(2C)) With the sides now expressed in terms of R and angles of the triangle, we can now ~~solve all of mathematics~~ represent pretty much anything we want. To get the heights of the triangle AD, BE, CF: |AD| = c*sin(B) = R*sqrt(2-2cos(2C))*sin(B) Likewise: |BE| = a*sin(C)= R*sqrt(2-2cos(2A))*sin(C) |CF| = b*sin(A)= R*sqrt(2-2cos(2B))*sin(A) To get the chord along the heights AD', BE', CF': ∠D'AC=∠DAC=∠EBC (DAC and EBC are similar) Similarly: ∠E'BA=∠EBA=∠FCA ∠F'CB=∠FCB=∠DAB Let α=∠FCA, β=∠DAB, γ=∠EBC. Then β+γ=A, α+γ=B, α+β=C. Of the equations, adding two and subtracting one and then dividing by 2 gives: α=(-A+B+C)/2, β=(A-B+C)/2, γ=(A+B-C)/2. We also have: ∠D'BC=∠D'AC=γ (subtend same arc/chord) ∠AD'B=∠ACB=C (subtend same arc/chord) ∠ABD'=∠ABE+∠EBC+∠CBD' = α+2γ That gives, by the sine law: |AD'|/sin(∠ABD') = |AB|/sin(∠AD'B) so |AD'| = sin(α+2γ)*c/sin(C) = sin(A/2 + 3B/2 - C/2)*R*sqrt(2-2cos(2C))/sin(C) Likewise: |BE'| = sin(B/2 + 3C/2 - A/2)*R*sqrt(2-2cos(2A))/sin(A) |CF'| = sin(C/2 + 3A/2 - B/2)*R*sqrt(2-2cos(2B))/sin(B) Actually, there is an easier way to get |AD'|, |BE'|, |CF'|; I already knew about it but I didn't realize just how easy it was until I thought about it again. I'll let p4wn3r tell you.

Posted: 10/31/2018 9:45 AM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

You can simplify some formulae. OAB, OBC and OCA are isosceles triangles. By tracing their altitude you can find a = 2R*sin(A) b = 2R*sin(B) c = 2R*sin(C) Alternatively, plug cos(2A) = 1 - 2sin(A)^2 in your answer and this form will follow. Then the altitude is AD = 2R*sin(B)*sin(C) The rest is just a cyclic version of that formula. In words, the height is twice the circumradius multiplied by the sines of the two other angles. Now, for AD', notice it's a chord. The length of a chord is determined by the radius and the angle of the arc its endpoints make on the circle. Look at the intersecting chords AD' and BC. The angle BDD' is the arithmetic mean of the arc angles BD' and CA. But that angle is pi/2, so that means BD' = pi - CA. Therefore, the arc AD' in counterclockwise direction (or, equivalently, the angle AOD') is equal to pi-2B+2C. We can apply the same construction we used to find the sides to find AD', the triangle OAD' is isosceles, etc. We find AD' = 2R*sin(pi/2 - B + C) = 2R*cos(B-C) And cyclically for the rest. In words, the extended height equals twice the circumradius multiplied by the cosine of the difference of the two other angles. The order you subtract the angles doesn't matter, since cos is an even function. Fractal's formulae simplify to this. The two trigonometric factors at the end simplify to 2. For the first factor, add and subtract C/2 in the formula for AD' and put A+B+C=pi, then sin(pi/2 + C - B) appears, which gives the previous formula.

Posted: 10/31/2018 7:58 PM

Quote

FractalFusion

Editor, Skilled player (1939)

Joined: 6/15/2005
Posts: 3247

I realized some time ago that for AD', all you need to do is this: ∠BAD = pi/2-B ∠BAO = (pi-∠AOB)/2 = pi/2 - C ∠DAO = ∠BAO-∠BAD = B-C Therefore AD' = 2R cos(B-C). Similarly, BE' = 2R cos(C-A) and DF' = 2R cos(A-B). I never bothered checking what happens if the triangle is obtuse (here O would be outside the triangle and two of D, E, F lie on extensions of the sides).

p4wn3r wrote:

The angle BDD' is the arithmetic mean of the arc angles BD' and CA.

This doesn't seem to me to be intuitive. Did you mean to say ∠BDD'+∠CDA = ∠BOD'+∠COA?

Posted: 10/31/2018 9:15 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

FractalFusion wrote:

p4wn3r wrote:
The angle BDD' is the arithmetic mean of the arc angles BD' and CA.
This doesn't seem to me to be intuitive. Did you mean to say ∠BDD'+∠CDA = ∠BOD'+∠COA?

Yes. This is just Theorem 4 here: https://mathbitsnotebook.com/Geometry/Circles/CRAngles.html The theorems there are all generalizations of the inscribed angle theorem. You prove them all in a similar way, by drawing isosceles triangles and checking the angles.

Posted: 11/1/2018 9:33 AM

Quote

Warp

Banned User, Former player

Joined: 3/10/2004
Posts: 7698
Location: Finland

In the most recent episode of Numberphile, the university professor Tony Padilla is interviewed about "the most evil number", 1000000000000066600000000000001, which happens to also be prime. It's noted that some of the numbers in the form of 1(n zeroes)666(n zeroes)1 are prime. In an extra video he tells how he started wondering if any numbers in the form 1(n zeroes)616(n zeroes)1 are prime, and says that he checked all the numbers up to a hundred thousand digits, and found no primes. It appears that even university math professors can sometimes miss the obvious, because it's quite trivial to see that numbers of that form can never be prime.

Posted: 11/1/2018 4:40 PM

Quote

BrunoVisnadi

Editor, Skilled player (1410)

Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil

Warp wrote:

In the most recent episode of Numberphile, the university professor Tony Padilla is interviewed about "the most evil number", 1000000000000066600000000000001, which happens to also be prime. It's noted that some of the numbers in the form of 1(n zeroes)666(n zeroes)1 are prime. In an extra video he tells how he started wondering if any numbers in the form 1(n zeroes)616(n zeroes)1 are prime, and says that he checked all the numbers up to a hundred thousand digits, and found no primes. It appears that even university math professors can sometimes miss the obvious, because it's quite trivial to see that numbers of that form can never be prime.

I just watched that segment and my impression is that he was just joking to argue the beast number is 666 instead of 616.

My YouTube channel: https://www.youtube.com/channel/UCVoUfT49xN9TU-gDMHv57sw Projects: SMW 96 exit. SDW any%, with Amaraticando. SMA2 SMW small only Kaizo Mario World 3

Posted: 11/1/2018 7:02 PM

Quote

Warp

Banned User, Former player

Joined: 3/10/2004
Posts: 7698
Location: Finland

BrunoVisnadi wrote:

I just watched that segment and my impression is that he was just joking to argue the beast number is 666 instead of 616.

When he says "and I searched for up to n equals a hundred thousand... and no prime numbers", I don't get that impression. I really get the impression that he did use a program to test all the numbers of that form up to that size. I believe that if he had realized that no numbers of that form can be prime, he would have said so, and explained why.

Posted: 11/2/2018 4:50 AM

Quote

FractalFusion

Editor, Skilled player (1939)

Joined: 6/15/2005
Posts: 3247

I want to mention that, as you get into the tens of thousands of digits, you have to be extremely careful when talking about prime numbers. There is an ever increasing misuse of the term "prime" to mean "probable prime" (a usage I will not defend), the reason being that it takes far less computation to establish a number as a probable prime compared to actually proving that it is prime. For example, OEIS has a list of indices of "prime" Fibonacci numbers, and the very first comment is "Some of the larger entries may only correspond to probable primes." Which means of course that the entry freely admits to making claims without proof. It would be accurate to say instead that it is a list of indices of probable prime Fibonacci numbers. Now regarding the Numberphile video, some context. Even when checking just for probable primes, the amount of computation required to check everything up to "n equals a hundred thousand", in general, is far more than warranted for someone who is casually doing it "just to see what happens". However, there is a catch. It is possible that a primality-testing program can determine all of them to be composite in a reasonable amount of time precisely because they are all divisible by 3. Even a trial division program can achieve this (though you'd never want to use such a program to prove that a hundred thousand digit number is prime). I still think it would be dumb to actually go through checking it up to a hundred thousand without checking beforehand that there is such an easy solution, especially since the use of primality testing tools requires a certain level of mathematical competence from the user. I think it is more likely that the people in the video are playing dumb, trying to sell 666 as superior to 616 for dramatic effect because 616 "somehow" fails to produce primes; the effect would be ruined if they said why this was the case.

Posted: 11/2/2018 11:29 AM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

Warp wrote:

It appears that even university math professors can sometimes miss the obvious, because it's quite trivial to see that numbers of that form can never be prime.

I can tell you how unsurprising this situation is. There are many "research" departments where all they do is learn and teach people how to run some software packages and publish whatever it spits out without having any idea of what they're doing. They're essentially technicians who specialized in some very specific software, but universities keep hyping them up to get money. About probable primes, it's actually more sane than other fields. Some of these tests would actually be rigorous if the Riemann hypothesis is proven true, so you can treat some of them as conditional proofs of primality. There are many other fields where what the program is doing involves lots of approximations and when they get the right answer no one knows if it's because of the theory or the approximation somehow canceled the error. Many times there are no precise instructions on how to repeat the calculation and the paper is nothing more than advertisement. Some fields are just plain bogus. When someone publishes that their program calculated a value that was observed in an experiment you can be sure he just ran 30 different codes and published the one that worked. There are some pretty dumb cases where some people announced a measurement, then later said it was wrong and put a new value. And meanwhile people always managed to come up with codes that "calculated" both values! That said, I have seen more awareness from the media about these issues and these "junk science" things are getting a hit in funding, which is a good thing.

Posted: 11/2/2018 5:05 PM

Quote

Warp

Banned User, Former player

Joined: 3/10/2004
Posts: 7698
Location: Finland

FractalFusion wrote:

I want to mention that, as you get into the tens of thousands of digits, you have to be extremely careful when talking about prime numbers. There is an ever increasing misuse of the term "prime" to mean "probable prime" (a usage I will not defend), the reason being that it takes far less computation to establish a number as a probable prime compared to actually proving that it is prime.

On the other hand, proving that a number is not prime (and consequently that "there are no numbers of this form within this range that are prime") is much easier, as with most of those primality tests if they say "not prime", that's a certainty. I suppose that when it comes to Mersenne primes, and the search of them, it's lucky that we have a quite efficient algorithm that gives a sure answer either way. All known Mersenne primes are that for certain (barring some strange bugs in the programs used by GIMPS.)

Posted: 11/7/2018 11:16 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

One of my friends sent me a problem that's insane. Prove that sqrt(8-sqrt(8+sqrt(8-...))) = 1 + 2sqrt(3)sin(pi/9) The pattern of signs on the infinitely nested radical is -,+,-,-,+,-,-,+,-,... This problem is from legendary indian mathematician Srinivasa Ramanujan. It takes a lot of calculations, it might be a good idea to use a computer algebra system to help. Even though I had seen a lot of problems like this, it took me a lot of time to see the idea. At first I thought my solution was a brute-force way, but then I saw it was Ramanujan's intended approach. Hint: The obvious way to deal with infinite radicals is to realize that taking away one period of the iteration does not change the limit. Then: x = sqrt(8-sqrt(8+sqrt(8-x))) The problem is that by denesting you get an equation of degree 8, which has no obvious solution. Suppose that the pattern was instead +,+,+,+,+,... Then it's not necessary to use three radicals, and you can do instead x = sqrt(a+x) And you get a quadratic, which obviously has a spurious solution. Try to understand what this spurious solution actually means. Now generalize, consider you have a system: x^2 = y + a, y^2 = z + a, z^2 = x + a Apparently this computes sqrt(a+sqrt(a+sqrt(a+...))), but think about the spurious solutions. What would they compute? Can you use that information to factor the degree 8 polynomial that comes up when you denest everything? Also, look at the value sin(pi/9). It would come up by trisecting pi/3 with a trigonometric relation, which is a cubic equation. Can you make a cubic appear in the octic polynomial?

Posted: 11/9/2018 3:20 AM

Quote

FractalFusion

Editor, Skilled player (1939)

Joined: 6/15/2005
Posts: 3247

p4wn3r wrote:

Prove that sqrt(8-sqrt(8+sqrt(8-...))) = 1 + 2sqrt(3)sin(pi/9) The pattern of signs on the infinitely nested radical is -,+,-,-,+,-,-,+,-,...

Consider equations of the form x=±sqrt(8±sqrt(8±sqrt(8-x))). It is easily shown that for each choice of ±, there is exactly one solution in [-7,7], and fixed-point iteration in [-7,7] converges to it (see http://mathonline.wikidot.com/the-convergence-of-the-fixed-point-method for the criterion). Since every solution is a root of ((x^2-8)^2-8)^2-8+x, which is degree 8, it follows that the roots of ((x^2-8)^2-8)^2-8+x satisfy exactly one equation of the form x=±sqrt(8±sqrt(8±sqrt(8-x))). It remains to show that x=1+2sqrt(3)sin(pi/9) satisfies x=sqrt(8-sqrt(8+sqrt(8-x))). It is easily shown that 1+2sqrt(3)sin(pi/9) is a root of x^3-3x^2-6x+17 (trigonometric solution of casus irreducibilis) which in turn divides ((x^2-8)^2-8)^2-8+x. Therefore x=1+2sqrt(3)sin(pi/9) satisfies exactly one of x=±sqrt(8±sqrt(8±sqrt(8-x))). Finally, 1+2sqrt(3)sin(pi/9) is between 2.1 and 2.2; this numerically verifies the signs to be +,-,+. QED. (I used WolframAlpha to cheat but I don't think I can come up with this any other way.) By the way, I noticed that x → 8-x^2 is a one-to-one mapping on all the roots of ((x^2-8)^2-8)^2-8+x. In fact, since 8-α^2 is always in the field extension Q(α) (using field theory here), x → 8-x^2 maps each root to a root (possibly itself) with the same minimal polynomial (Edit: I messed up here, not sure how to fix it yet). Since x → 8-x^2 has period 1 or 3 for all roots (because ((x^2-8)^2-8)^2-8 = -x), and the only solutions with period 1 are roots of x^2+x-8 (the all-positive and all-negative cases), it follows that all other roots have period 3, and so must necessarily be degree 3 or 6. It happens that they are degree 3 here; this doesn't necessarily apply if the 8's are replaced by another number. In case anyone is wondering, the full factorization of ((x^2-8)^2-8)^2-8+x over the integers is (x^2+x-8)(x^3-3x^2-6x+17)(x^3+2x^2-11x-23).

Posted: 11/9/2018 2:10 PM
(Edited: 11/10/2018 1:20 PM)

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

I used a different sign convention to solve it, but I could factor it in the general case. The system is x^2 = y + a, y^2 = z + a, z^2 = x + a We have x = ((x^2-a)^2-a)^2-a or x^8 - 4ax^6 + 2(3a^2-a)x^4 - 4(a^3-a^2)x^2 - x + a^4 - 2a^3 + a^2 - a = 0 Now, as Fractal said, because of the ambiguity of the square root sign, the roots of the equation are related to all possible patterns of signs in the infinite nested radical. If x=y=z then this reduces to the quadratic x^2-x-a = 0, which should factor the previous polynomial. The quotient is x^6 + x^5 + (1-3a)x^4 + (1-2a)x^3 + (1-3a+3a^2)x^2 + (1-2a+a^2)x + 1 - a + 2a^2 - a^3 = 0 Now, the roots of this are part of a "limit cycle" corresponding to the -+- and +-+ patterns. If we're going to use field theory, we can look at the Galois group by seeing which changes of the roots preserve the equations of the limit cycle. If x,y,z are in a cycle, then the mappings (x,y,z)->(y,z,x)->(z,x,y) preserve the relations, but arbitrary permutations should not. Therefore, the Galois group should be generated by two cyclic Z3 groups, and another Z2 group that switches 3 roots from one cycle to the other. That means the sextic should factorize into two cubics after solving a quadratic. (Whenever I look at an identity from Ramanujan, I think I am seeing something from a higher intelligence. It's amazing how he could see the factorization without any formal education in algebra. The only explanation I have for this is that he somehow developed an intuition of Galois theory after solving lots of algebraic equations) In any case, once you guess the factorization into cubics, it's easier. Set x+y+z=u. Summing the equations and using (x+y+z)^2 = x^2 + y^2 + z^2 + 2(xy+yz+zx), we find xy + yz + zx = (u^2-u-3a)/2 Now change the equations a bit: x^2 y = ay + y^2, x^2 z = az + yz y^2 z = az + z^2, y^2 x = ax + zx z^2 x = ax + x^2, z^2 y = ay + xy Sum everything and use (x+y+z)(xy+yz+zx) = x^2 y + y^2 z + z^2 x + x^2 z + y^2 x + z^2 y + 3xyz You should get xyz = (u^3 - 2u^2 - (1-7a)u - 3a)/6 Therefore x,y,z are roots of the cubic x^3 - ux^2 + x(u^2-u-3a)/2 - (u^3-2u^2-(1-7a)u -3a)/6 = 0 Now write the same thing for u -> v, and when you multiply the two cubics, you should get the sextic! The coefficient of x^5 gives u+v=-1 The coefficient of x^4 gives a triviality when substituting u+v=-1. The coefficients of x^3 give uv = 2 - a Solving the quadratic, the factorization magically works and you get the polynomial x^3 + x^2(1+sqrt(4a-7))/2 - x(2a+1-sqrt(4a-7))/2 + (a-2-a sqrt(4a-7))/2 = 0 The other is found by flipping the sign of the square root. Now you can solve this by depressing the cubic and matching with a trigonometric relation. This is boring, the root that matters is, when tan(p) = (2sqrt(4a-7)-1)/3sqrt(3), x = -(1+sqrt(4a-7))/6 - 2sqrt(4a-sqrt(4a-7))sin(p/3)/3 Now, amazingly, when a = 8, sqrt(4a-7) = 5 and tan(p) = sqrt(3)! So, p = pi/3 and x = -1 -2sqrt(3)sin(pi/9) With my sign convention, it appears negative. To prove that x = -sqrt(8-sqrt(8+sqrt(8-...))) You can use numerics or just plug the solutions in the system, which you can check with trigonometric identities. (1+2sqrt(3)sin(pi/9))^2 = 8 - (1+2sqrt(3)sin(2pi/9)) (1+2sqrt(3)sin(2pi/9)^2 = 8 + (-1+2sqrt(3)sin(4pi/9)) (-1+2sqrt(3)sin(4pi/9))^2 = 8 - (1+2sqrt(3)sin(pi/9)) Nesting this, you can convince yourself that the pattern is -+-,-+-,... Although there's of course the question of convergence that I didn't bother to check...

Posted: 11/10/2018 7:52 AM

Quote

FractalFusion

Editor, Skilled player (1939)

Joined: 6/15/2005
Posts: 3247

So it does turn out that there is a nice factorization of the sextic into cubics in general, even though it's not over the integers (except when 4a-7 is a square). By the way, the (a-2-a sqrt(4a-7)) should be over 2; that is, (a-2-a sqrt(4a-7))/2.

p4wn3r wrote:

Therefore, the Galois group should be generated by two cyclic Z3 groups, and another Z2 group that switches 3 roots from one cycle to the other.

This is probably beside the point, but finding Galois groups is quite complicated and I can't be certain that the Galois group has to be Z3×Z3×Z2 (unless there's something I'm missing). Yes it's true that, if we look at the problem purely as a permutation of 6 roots (that is, the maximal subgroup of S6 satisfying the cycle conditions), then it is Z3×Z3×Z2. But Galois groups have additional properties because they describe automorphisms over Q. I can say that if 4a-7 is a square number (which happens when a=8), then from your factorization we get two cubics over the integers. Since automorphisms over Q can only map roots to roots within the same minimal polynomial, you can't switch the roots of one polynomial with the roots of the other. So in this case it is not possible to get Z2 in there. The second Z3 also makes the assumption that the roots of one cycle are "independent" of the other cycle. That is not necessarily so and I made that mistake in my previous post. E.g. Q(sqrt(2)) and Q(sqrt(2)+1) are the same field even though the minimal polynomials of sqrt(2) and sqrt(2)+1 are x^2-2 and (x-1)^2-2=x^2-2x-1, respectively. Indeed, the Galois group of (x^2-2)(x^2-2x-1) is not Z2×Z2, but Z2. However, I don't really have a strategy for how to determine whether the second Z3 should be included or not.

p4wn3r wrote:

... just plug the solutions in the system, which you can check with trigonometric identities. (1+2sqrt(3)sin(pi/9))^2 = 8 - (1+2sqrt(3)sin(2pi/9)) (1+2sqrt(3)sin(2pi/9)^2 = 8 + (-1+2sqrt(3)sin(4pi/9)) (-1+2sqrt(3)sin(4pi/9))^2 = 8 - (1+2sqrt(3)sin(pi/9))

That would have been a nice way to reduce the proof to a few lines, and this was my first line of thought. Unfortunately I couldn't find a way to prove the identities within any reasonable amount of brainpower (it seems you have to use the minimal polynomial of sin(pi/9) somewhere), so I settled for proving it is the solution to one of x=±sqrt(8±sqrt(8±sqrt(8-x))) based on polynomials (which seems easier) and using numerics to figure out which one it is.

p4wn3r wrote:

Although there's of course the question of convergence that I didn't bother to check...

It shouldn't be too hard to check. The most concise version I have to prove this and other similar fixed-point iteration methods (like infinite nested radicals) is the criterion for convergence of fixed-point iteration (Theorem 1) which I linked in my previous post. I'll add a bit of detail below. If we let g(x)=±sqrt(8±sqrt(8±sqrt(8-x))) and consider [-7,7], you just have to check that whenever -7<x<7, we have -7<g(x)<7 as well as |g'(x)|<1. In fact 1<|sqrt(8-x)|<4 → 2<|sqrt(8±sqrt(8-x))|<4 → 2<|g(x)|<4, so these can be established easily. This proves not only that g(x)=x has a unique solution in [-7,7], but also that fixed-point iteration g(g(g(...g(g(c))...))) converges to this solution when the starting value c is in [-7,7]. You can also use a fixed-point iteration diagram to show convergence (for example, http://tasvideos.org/forum/viewtopic.php?p=459785#459785 ), but the diagram of this function is a little bit hard to get without resorting to WolframAlpha.

Posted: 11/10/2018 1:55 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

FractalFusion wrote:

So it does turn out that there is a nice factorization of the sextic into cubics in general, even though it's not over the integers (except when 4a-7 is a square). By the way, the (a-2-a sqrt(4a-7)) should be over 2; that is, (a-2-a sqrt(4a-7))/2.

Corrected. Thanks for taking a look!

FractalFusion wrote:

p4wn3r wrote:
Therefore, the Galois group should be generated by two cyclic Z3 groups, and another Z2 group that switches 3 roots from one cycle to the other.
This is probably beside the point, but finding Galois groups is quite complicated and I can't be certain that the Galois group has to be Z3×Z3×Z2 (unless there's something I'm missing). Yes it's true that, if we look at the problem purely as a permutation of 6 roots (that is, the maximal subgroup of S6 satisfying the cycle conditions), then it is Z3×Z3×Z2. But Galois groups have additional properties because they describe automorphisms over Q.

Perhaps I should have been more accurate and have said that the Galois group is a subgroup of Z2 x Z3 x Z3. I know that the root permutation approach has many limitations, because it ignores the subtleties of the field being extended. Another case where Z2 would not appear is if a was in a quadratic number field instead of a rational, it's possible that sqrt(4a-7) is denested, so does not generate a new field. The point is that, taking these subtleties into account does not help to understand why the factorization is possible. If you want to understand why you should try to factor the sextic in this problem and not a general one, the reason is that, the problem is formulated in a way that lets you see that in the worst case the Galois group is abelian, and thus solvable, unlike a general sextic.

Posted: 11/19/2018 10:34 AM

Quote

Warp

Banned User, Former player

Joined: 3/10/2004
Posts: 7698
Location: Finland

In one of his latest videos, blackpenredpen calculates the value of sin(i). He uses Euler's formula for this. But how do we know that Euler's formula is valid for complex values of the angle? The Wikipedia page says: "Euler's formula states that for any real number x". I don't see a mention (or denial) that it is also valid for complex values of x. The Wolfram MathWorld page doesn't seem to make any mention one way or the other.

Posted: 11/19/2018 1:33 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

The principle behind Euler's formula making sense for complex arguments is analytic continuation, you can look it up to understand it. The main idea is: there's no a priori answer to an expression like sin(i). There is an infinite amount of functions from the complex numbers to the complex numbers that match sin(x) in the real line. To see this, just pick any function that matches sin(x) on the reals and add one that is 0 for every real number but does not vanish in imaginary ones. These two functions will be different, but both are extentions of sin(x) to the complex plane. However, if you want this extension to be differentiable, then it's a completely different story. Calculus with complex numbers is much more different than with the reals. While it's completely possible that a real function is differentiable once but not twice or more, in the complex plane if it has only the first derivative, that means it will have infinitely many derivatives and that its Taylor series will converge for some small enough radius. The consequence of this is that requiring a function to be complex differentiable is very restrictive. In particular, it implies that there's only one function that extends sin(x) and is differentiable (or analytic, which in complex numbers is the same thing). To prove Euler's formula you only need to look at the Taylor series of e^x, sin(x) and cos(x). If you treat this series as a sum of complex numbers instead of reals, you will see that it converges just as well, and the function you obtain from it is guaranteed to be the analytic continuation of them, so you can safely interpret Euler's formula as a relation between complex numbers.