Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
More abstract nonsense. Now we're gonna start having fun with arrow chasing!
p4wn3r wrote:
A category consists of a collection of objects, and for each pair of objects, a set of morphisms between them. The collection of objects of a category C is often denoted obj(C), but we will usually denote the collection also by C. If A,B are in C, then the set of morphisms from A to B is denoted Mor(A,B).
Morphisms compose as expected. If f is in Mor(A,B) and g is in Mor(B,C), there is a morphism g o f in Mor(A,C). Composition is associative. For each object A in C, there is the identity morphism idA: A -> A, such that every morphism that's composed with it, either left or right, returns the same morphism. A morphism f is called an isomorphism if there is a (necessarily unique) morphism g such that both f o g and g o f are the identity morphism.
We need more definitions for this exercise. A (covariant) functor is a map between categories that preserves morphisms, that is, a functor F: C -> D between categories C and D associates to each object X in obj(C) an object F(X) in obj(D), and for each morphism f in Mor(X,Y) a morphism F(f) in Mor(F(X),F(Y)) such that the following holds:
(1) F(idX) = idF(x)
(2) F(g o f) = F(g) o F(f)
Functors, of course, compose with each other. If we have F: C -> D and G : D -> E, the functor G o F: C -> E, exists. There's also the identity functor I : C -> C
A natural transformation is a map between two functors F,G: C->D, that "preserves internal structure". Formally, a natural transformation n: F -> G associates to every object X in obj(C) a morphism nX: F(X) -> G(X) between objects in D, such that:
(*) For every morphism f: X->Y in C, we have nY o F(f) = G(f) o nX
A better way to visualize this condition is using a commutative diagram, where every composition of morphisms along a path connecting a pair of vertices is understood to be equal:
Now, for the problems. It might help to represent diagrams for natural transformations in the style of the Wikipedia article:
(1) If we have two natural transformations n: F -> G and m: G -> H, where F,G,H: C -> D (that is, all of them are functors from category C to category D), show that we can compose them, and that composition has the structure of a monoid (it's associative and has an identity). This is the so-called vertical composition of natural transformations.
(2) If we have a natural transformation a: F -> G, where F, G: C->D, and a functor H: D -> E, show that we can find a natural transformation from H o F to H o G, called the right whiskering of a with respect to H.
(3) Similarly, show that if we have a natural transformation b: G -> H, where G,H: D -> E, and a functor F: C -> D, show that we can find a natural transformation from G o F to H o F, called the left whiskering of b with respect to F.
(4) Finally, if we have two natural transformations a: F-> G and b: H -> K, where F,G : C -> D and H,K: D-> E, show that we can define the horizontal composition b o a : H o F -> K o G in two ways:
(a) Left whiskering followed by right whiskering
(b) Right whiskering followed by left whiskering
Also, show that the definitions (a) and (b) define the same natural transformation.
Bonus: why are they called vertical and horizontal composition?
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Warp wrote:
Wouldn't it be a contradictory concept to state that a non-convergent sum converges to a finite value? It's either convergent or non-convergent. It cannot possibly be both at the same time.
Wow, really? Are you reading ANY of my posts now?
In any case, no, it's not, as was discussed a few posts ago, to discuss convergence you need the concept of a metric, which tells you which numbers are close together. In the question I asked, I gave the example 1 + 2 + 4 + 8 + ..., which diverges in the usual metric, but converges to -1 in the 2-adic metric. Watch the 3blue1brown video if that helps (which I also linked before, by the way).
The discussion that we had, which was totally reasonable, was whether it's possible to arrive at the result 1+2+3+...=-1/12 without complex analysis, which I think is totally possible. There is this derivation, common in physics, where one introduces an exponential regulator. It's possible to define a metric where functions that differ by a pole of the form 1/epsilon^2 are very close together, so that the summation does, in fact, converge to -1/12.
The introduction of the exponential term also explains why blackpenredpen's way of summing terms gives a different value. His method relies on the fact that the average of an odd number of consecutive integers is the integer in the middle. Once the terms are modified with the regulator, that property is no longer true, and this method, in particular, fails. The right way to do this without invoking the regulator is to use a graded ring, which is a more advanced concept.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Warp wrote:
p4wn3r wrote:
Cool! I decided to post this problem because I thought the Mathologer answer to the -1/12 video was too shallow.
The sum of all natural numbers is not -1/12, because it's actually -1/8.
(I'm quite certain that you can make it equal to whatever number you want.)
I'm also quite certain that you will ignore what I am writing, but I'll do so anyway. In most theories where people try to find axioms where the sum can be defined as convergent, the structure where they are summed over is a monoid that induces a gradation in the summed elements, so this gobbling up of element that he does is not allowed.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
P.JBoy wrote:
If you're looking for another one that W|A can't solve:
for |α| > 1
Call the integral I(alpha). First, perform the change of variables x -> pi - x. It follows that I(alpha)=I(-alpha). From this, it is true that I(alpha) = 1/2*(I(alpha)+I(-alpha)). Explicitly:
The last expression can be rewritten in terms of the original integral:
(1)
Another relation is:
(2)
From(2), it follows that I(0)=I(1)=0.
Assume 0<alpha<1, then if we iterate (1):
At the limit n-> infinity, the RHS tends to 0. So, I(alpha) = 0 for 0<alpha<1.
Now, if alpha>1, we simply apply (2) and conclude I(alpha) = pi log(alpha^2). Since I(alpha)=I(-alpha), that also applies to alpha<-1, and we have found the answer.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Congratulations! I posted this to some math groups I participate and it seems to have stumped everyone. You are the first to provide an answer. I have two other solutions besides the reduction to the integral of x^(2/5)/(1+x^2), but I'm too busy at the moment to write them down here. Here are the hints for each one if you want to reproduce them.
HINT 1: Look at the original integrand. Is it even? Is it periodic in the imaginary axis? Can you solve it with a rectangular contour?
HINT 2: Expand cosh(2x/5) as a Taylor series. Look up the Euler numbers
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
FractalFusion wrote:
The way you are describing p-adic completion at "p=1" (???) and the "mysterious field with one element" only makes me think there are better ways to describe ζ(-1).
By the way, it is pretty clear that a lot of people see the Numberphile calculation as nonsense. That is entirely on Numberphile. There are ways to present ζ(-1) and other similar series without it coming across as nonsense.
I think this all boils down to what "better" is. If the goal is to grade people's answers as right or wrong by applying what's in a book, then I guess it's pretty annoying to have the high schoolers who watch numberphile come up with 1 + 2 + 3 + 4 + ... = -1/12
However, if by "better" you understand something that can potentially solve open foundational problems, then it should not be a problem to communicate speculative ideas. I liked a lot 3B1B's video, especially the part where he says "you are a mathematician, not a robot".
In this context, I think the questions raised by Frenkel in the Numberphile video are spot-on. In very different contexts, the sum of natural numbers, or their cubes, and so on, pops up. And in quantum field theory, algebraic number theory, string theory, etc., assigning -1/12 to the series makes everything work. Quantum Field Theory, although not rigorously established, predicts outcomes of physical experiments with an accuracy of one part in one billionth, it's crazy to doubt its validity.
By the way, I don't claim that my "p=1" picture is adequate. If I did, I would not post it here, I would submit it as a solution to the Riemann hypothesis. All that I am saying is that it's perfectly reasonable to define something where 1+2+3+4+...=-1/12 independent of the zeta function, since this would explain lots of things.
If Mathologer thinks that, in the specific case of zeta(s), this is not possible to do, it's a completely reasonable position. All I can say is that if previous mathematicians assumed that, we would not have foundational results proven, like the finiteness of the ideal class group for a number field, or the Weil conjectures, because their proofs go into an opposite direction. In any case, if he thinks that, he's welcome to do what everyone else does: publish a paper about it.
FractalFusion wrote:
Is it not possible to prove that ζ(-1)=-1/12 using analysis in complex numbers only? If it is possible, then I wouldn't expect anyone to bring in p-adics when it is not necessary to do so.
You know, just as a sanity check, I decided to watch the Mathologer video again and see if he does prove this value of zeta using complex analysis. It turns out that he doesn't. In the part about analytic continuation, he suggests an analytic function defined in an open subset of the complex plane defines it completely. While this is true, it is no guarantee that you can extend it to the entire complex plane.
It might happen that the analytical continuation runs into an infinite number of singularities, like the prime zeta function, or modular forms in general, which cannot be continued to the lower half-plane. If he did prove it using complex analysis, why doesn't he mention stuff like the functional equation or the Euler transform of the zeta function, which justify its extension to the whole plane?
I think he knows this, as he mentions people will nitpick him to death in the comments. This is plain old hypocrisy for me, requiring others to display an enormous amount of rigor about something that's mostly speculative, while not even bothering to apply correctly the results that are already established.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Flip wrote:
In general:
(p-1) + (p-1)p + (p-1)p2 + (p-1)p3 + ... = -1
To see this, just add 1 to the sequence.
[...]
So adding 1 to the sequence gives 0, hence what we started with must be equal to -1.
I love arguments like this! It reminds me of an anecdote I heard sometime ago, after seeing the teacher prove 0.999... = 1, asked whether .....99999 = -1, essentially because of this. Of course, his ideas were too deep to be appreciated at that situation.
FractalFusion wrote:
I solved it. I just never bothered to tell you.
It is conceptually easy once you understand p-adics.
Cool! I decided to post this problem because I thought the Mathologer answer to the -1/12 video was too shallow. The numberphile calculation is indeed not rigorous, it would require a p-adic completion at "p=1", which we still can't make sense of, but it's far from "nonsense". It's related to the mysterious field with one element, that people have trouble defining, but has the potential to solve lots of problems.
It looks like Mathologer has no idea that non-archimedean completions exist, and I don't think it's too much to expect someone to understand a little of the subject they are talking about before dismissing it as nonsense.
FractalFusion wrote:
I mentioned that there are paradoxes when p=0.5. This is because, as you said, the expected number of bacteria after N events, starting from 1 bacterium, is (2p)^N. When p=0.5, the expected number of bacteria is 1, which may indicate that the colony may survive with positive probability. Yet, as we have figured out, the colony is guaranteed to die out eventually.
So, that was the paradox you were mentioning. I understood the p=1/2 case as an instance of gambler's ruin (second bullet point in Wikipedia).
------------------------
Ladies and gentlemen, I present to you my newest integral:
Prove it! I am very proud of this one because I finally managed to come up with something that Wolfram Alpha could not find the exact value in its standard computation time. This is getting harder and harder to do as the software evolves.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
p4wn3r wrote:
So, for this exercise, replace the usual absolute value of the real numbers with p-adic norm for p=2, also known as the 2-adic norm or the dyadic norm. Prove that, with respect to this metric:
1 + 2 + 4 + 8 + ... = -1
Well, it seems no one solved it. It's not very hard, though.
Recall the notions we need to define "convergence". The real numbers arise when we introduce a norm in the field of rational numbers, and define them as equivalence classes of Cauchy sequences.
The norm must satisfy some properties:
(1) |x| >= 0
(2) |x| = 0 => x = 0
(3) |xy| = |x||y|
(4) |x+y| <= |x| + |y|
The p-adic norm is defined as follows. 0 has norm 0, while for any nonzero negative number, we may write it uniquely as x = p^n*a/b, where a and b are coprime and not divisible by p, and n is any (possibly negative) integer. In this case |x| = p^(-n)
It's possible to prove that this norm satisfies all properties (1)-(4). In fact, it satisfies a stronger version of (4): |x+y| <= max(|x|,|y|). This relation is usually called the non-archimedean triangle identity. Anyway, since (1)-(4) are satisfied, the convergence theorems in the reals all hold for p-adic numbers.
In particular, the series 1 + 2 + 4 + 8 + ... converges to - 1 if the sequence of partial sums sn satisfies |s(n)+1|<epsilon, after some number N(epsilon).
In fact, we have s(1) = 1, s(2) = 3, s(3) = 7, ..., s(n) = 2n-1. So, |s(n)+1| = |2^n| = 2^(-n) <epsilon> -log2(\epsilon), we satisfy the required identity.
Another way is to prove convergence, without calculating the value. For example, the n-th term added, 2^n, has norm 2^(-n), and by the ratio test, the series should converge. Therefore, you are allowed to do crazy stuff like:
S = 1 + 2 + 4 + 8 + ... = 1 + 2(1+ 2 + 4 + ...) = 1 + 2S => S = -1
If anyone is still interested in exercises like this, another one would be proving
1 - 2 + 4 - 8 + 16 - ... = 1/3
Again, using the 2-adic norm. It's the same idea.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
r57shell wrote:
p4wn3r wrote:
Now, if the game is fair, it should also be fair when the sequence of coin flips HHTT just showed up.
What means to be fair at some moment?
It means that, if the game, played infinitely, is fair, then the game, when it's played only until the sequence HHTT shows up, should also be fair.
r57shell wrote:
p4wn3r wrote:
At that point, the casino got t dollars from gamblers and had to pay back 16 dollars to the gambler that won.
How do you calculate that at some moment they spent X money? It looks like "out of thin air".
We can see the game as: every turn a gambler arrives and gives a dollar to the casino. When a gambler gets N coin flips right, the casino loses 2^N.
r57shell wrote:
p4wn3r wrote:
E[t-16]=0
Where this equation came from? What is t?
t is the amount of dollars the casino receives from gamblers, which, by the arguments above, is also the number of turns on average that it takes for the sequence HHTT to show up. Since the game is fair, the expected balance is 0, which means that the number of turns on average for the sequence to show up is 16.
r57shell wrote:
Looks like, you not calculating expectation. You just calculate balance of casino.
The whole point of the argument is that the balance of the casino is intrinsically tied to the expected number of turns for the sequence to show up. They are so tied together, that evaluating the balance allows you to evaluate the expected number of turns.
----------------------------
Now for another problem. Some time ago there was a lot of discussion on the internet about the sum of all natural numbers. In the video I linked, Frenkel gives his interpretation of the formula that sets this value to -1/12.
I will give my point of view looking at it from algebraic number theory, which, although many people say it's an area of math, it is not. It is a philosophy of life. One interesting theme that emerged from algebraic number theory around the first half of the 20-th century is that one should not privilege the real numbers as the most natural completion of the rationals. In fact, other completions like the p-adic numbers are possible, and in some ways are more useful, and in fact can be used to give a rigorous definition of some nonsensical identities.
So, for this exercise, replace the usual absolute value of the real numbers with p-adic norm for p=2, also known as the 2-adic norm or the dyadic norm. Prove that, with respect to this metric:
1 + 2 + 4 + 8 + ... = -1
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
r57shell wrote:
p4wn3r wrote:
Now, if the game is fair, it should also be fair when the sequence of coin flips HHTT just showed up.
From this and after, I'm unsure.
OK, this result holds quite generally, but proving it indeed is tricky. So, because of that, I'll go into formalism (I warned you! :P)
What is a martingale? A martingale is a process that is "fair". One example is to keep flipping a coin and every time you get heads, receive 1 dollar, and for every tails, pay 1 dollar. As you can see, the expected return of playing this game is 0. Suppose you got really lucky and amassed 10 dollars playing this, it still makes no sense to keep playing, the expected return is still 0. Likewise, if you were unlucky and lost 10 dollars, it makes no sense to keep playing to recover money.
This is the idea of a martingale. After drawing from random variables, the information you get by looking at the sequence of draws (actually, in general, it's modeled as a filtration, but we don't need to get into theses details) does not help you increase your odds at all.
The game of the gamblers against the casino, where they win by guessing the coin results, and runs infinitely many times, is also a martingale. If we have a game that runs forever, if we set a condition for each to stop, (in our case, we stop the game when the sequence turns up), it's a general result that (subject to some conditions on the stopping procedure), the stopped process of a martingale is also a martingale, and thus, "fair".
Intuitively, think of it like this. Suppose you go to the casino with 50% chance of doubling, so that the expected return is zero. If the stopping process of this martingale were not a martingale, then you could beat the casino by going there, and doubling your bet every time you lose, and when you gain one dollar, leave. In fact, what happens is, you start with a finite amount of money, so you have a high chance of getting out of the casino 1 dollar richer, but have a small chance of losing everything, so the betting strategy does not help you at all.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Forget about my previous post about you needing a computer to find the expected value of different coin patterns. I dug up stuff on the internet and found out that there's an amazing method using martingales that destroys the problem!
If you want to Google it yourself, look for the Abracadabra problem. Anyway, I'll try to simplify the proof removing the martingale formalism.
Suppose you have a casino, and in your betting game you specify a sequence of N coin flips. Let me take HHTT as an example.
Suppose that, at each time n, a gambler arrives at the casino and bets 1 dollar. At this moment, this gambler will bet that H will come up, and the casino will flip the coin randomly.
If the gambler is correct, and the coin does come up heads, the casino will pay back 2 dollars. At the next event, the gambler will bet these 2 dollars in the next coin in the sequence (in our case H), notice that this does not stop the next gambler arriving at n+1! They always arrive, no matter what the coin flip turns out. For every gambler, if he's correct, he gets back double what he bet. If at any point the gambler is incorrect, he will simply lose his bet and leave the casino.
Notice that this game is fair for the gamblers, as can be seen by calculating their expected payoff. If the gambler gets the entire sequence of 4 coin flips right, they leave the casino with 2^4-1 = 15 dollars. If they lose at any point, they leave with -1 dollar. Calculating the odds
E = (1-2^-4)*(-1) + 2^-4*(2^4-1) = 0
If the game is fair for the gamblers, it's also fair for the casino. In particular, for every gambler that loses, the casino takes 1 dollar, and for every gambler that wins, the casino pays 2^4 - 1. Alternatively, for every event where a gambler arrives (no matter if he wins or loses), the casino takes 1 dollar. And for every winning gambler, pays back 2^4.
Now, if the game is fair, it should also be fair when the sequence of coin flips HHTT just showed up. Assume it takes on average t steps for this sequence to show up. At that point, the casino got t dollars from gamblers and had to pay back 16 dollars to the gambler that won. That means
E[t-16]=0, but since expected value is linear:
E[t] = 16
So it takes 16 steps for HHTT to show up!
Now, for HHHH, notice that when the last H flips, not only the gambler that bet on HHHH won, the three others who arrives after him and bet on HHH, HH, and H are also winning. So, in this situation, the casino must pay 16 + 8 + 4 + 2 = 30. So it takes 30 steps for HHHH to appear.
If you think about it, you can derive a formula, the number of steps is
t = sum(2^s) for every s>0 where the suffix of length s is also a prefix of the string.
In particular, for 10 H's, every suffix of length from 1 to 10 is also a prefix, so we must sum all powers of 2 from 1 to 10, which gives 2046, as mentioned earlier.
The method used is known as the optional stopping theorem. It looks scary, but it's basically my argument here, it has some ugly conditions (that's because for a general martingale, we cannot do the change of summation order we did here), but believe that they are satisfied in this problem.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
FractalFusion wrote:
You are studying a new strain of bacteria, Riddlerium classicum (or R. classicum, as the researchers call it). Each R. classicum bacterium will do one of two things: split into two copies of itself or die. There is an 80 percent chance of the former and a 20 percent chance of the latter.
If you start with a single R. classicum bacterium, what is the probability that it will lead to an everlasting colony (i.e., the colony will theoretically persist for an infinite amount of time)?
Extra credit: Suppose that, instead of 80 percent, each bacterium divides with probability p. Now what’s the probability that a single bacterium will lead to an everlasting colony?
Suppose that the probability of an everlasting colony is x. After a time lapse, the bacterium will either split or die. If it splits, we have two bacteria. The probability of both of them not generating an everlasting colony is (1-x)^2, so we'll have an eternal colony with probability 1-(1-x)²=2x-x².
Therefore, we have x = p(2x-x²), so either x=0, or 1 = p(2-x) => x = 2 - 1/p
Since x is a number between 0 and 1, the second solution only makes sense for p >= 0.5.
In particular, for p<0>0 for all N and still satisfy that limit.
Now, for p >0.5, I will argue that the correct solution is x = 2 - 1/p. If it were x=0, we would have that the expected number of bacteria after N events is 0, but it's in fact (2p)^N, which does not tend to 0 if p>0.5. So the probability should be positive, and therefore x = 2 - 1/p.
EDIT:
I might do this one as well:
Warp wrote:
What's the expected average number of times you'll need to toss the coin in order to get 10 of the same side consecutively?
I'll give a more formal derivation of Masterjun's answer. The ideas are already there. This process can be modeled as an absorbing Markov chain. They have many interesting properties.
Let us first start with the problem of getting all heads. You can model the problem as having 11 states.
0 -> 1 -> 2 -> 3 -> ... -> 10
For each state, you have 1/2 chance of going from state n to n+1, and one half of going from n all the way back to 0. If you reach 10, you stay there forever, it's what we call a terminating state.
Now, if we call E(n) the expected number of steps until we get to 10 when we start at n, we have
E(n) = 1 + E(0)/2 + E(n+1)/2,
and of course,
E(10) = 0
Rewriting, we get
E(n+1) = 2*E(n) - E(0) - 2,
so:
E(1) = E(0) - 2
E(2) = E(0) - 6
E(3) = E(0) - 14
...
E(n) = E(0) - 2^(n+1) + 2
Since E(10) = 0, we must have E(0) = 2^11 - 2 = 2046. If we just want N consecutive flips, the formula for the expected value is simply 2^(N+1) - 2.
Now, if we want either 10 heads or 10 tails, we could (if we want to) set up another Markov chain.
From an initial state 0, we can go to either 1H or 1T. From there, the chains differ:
1H -> 2H -> 3H -> 4H -> ... -> 10H
1T -> 2T -> 3T -> 4T -> ... -> 10T
The transition from (n)H -> (n+1)H has 1/2 probability. The other possibility is (n)H->1T, which also has 1/2 chance. 10H and 10T are terminating states.
The thing is: the H and T chains are completely symmetric, so the expected values for both of them should be the same. In practice, we can compress (1H,1T), (2H,2T), ..., into a single state.
At the end of the day we are left with a state 0 that goes to a Markov chain which is just like the previous one we discussed, with one node less.
Therefore, we should have E(0) = 1 + E(1) = 1 + 2^10 - 2 = 1023
I remember there's a way to transform problems like this into resistor networks, but I can't figure out how, right now.
--------------
An interesting challenge, which I think you need a computer to do, would be to find the expected value for finding 5 heads then 5 tails (or vice versa), that is, HHHHHTTTTT, or TTTTTHHHHH. The value should be less than 1023. Why?
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
FractalFusion wrote:
(Am I learning category theory just to answer p4wn3r's questions?)
I am actually very interested in the topic of whether it's possible to get someone to learn something by means of handing out simple exercises before presenting the theory, so feel free to share your experience doing this.
Anyway, I never understood why some people are so avert to categories. As I think this exercise makes clear, they can be seen as generalization of groups where you drop the closure and existence of inverse conditions. What's so wrong about studying that? I can understand some of the frustration, though. I find it completely baffling how people can sometimes write hundreds of pages when the idea is ridiculously simple, every author has a different definition of everything, and it becomes pretty much impossible to follow what's going on.
An example of this is the proof of Fermat's last theorem. Only chapters 3 and 5 are actually the novel arguments. Chapter 4 is an interesting idea that he tried, but did not work out. Chapters 1 and 2 are mostly setup, which is already in an equivalent form in the literature (although, to be fair, not neatly organized as in the paper). He could have written the same paper by simply stating Conjecture 2.16 and including chapters 3 and 5, which would reduce its length considerably. (To be clear, I don't claim to understand that proof, I still haven't got to that point and have no idea what's happening in Chapters 3 and 5, but I do understand how the main result follows if he can prove Conjecture 2.16). I won't even comment on the proposed solution to the abc conjecture, where it seems that no mathematician can understand the "proof" at all.
The main result that really sold me into category theory is BRST quantization. The usual procedure to quantize the theories used in particle physics is to start with an ill-defined functional integral, where you put complex and Grassmann numbers in the integrand, and applying a lot of algebra to reduce it to a Gaussian one. For the gauge fields, you introduce a magical identity to get rid of some ambiguities. In some cases, where we have chiral fermions, this can fail because of anomalies.
In BRST quantization (I think Wikipedia's definition is different from mine, so I won't even cite it here), the space where all particles live is defined to be a chain complex. The BRST operator s defines a cohomology in this complex iff s²=0. In this procedure, you write it in two parts: s = a + b, where both a and b define cohomologies, that is, a²=0 and b²=0. One of them corresponds to the part of reducing all fields to Gaussian integrals, and is a Koszul-Tate resolution, while the other, which corresponds to inserting the magical identity, is simply Lie algebra cohomology. In order to have s²=0, we must have ab+ba=0, meaning that they anticommute. It turns out that they always anticommute if the theory does not have chiral fermions, but they can also anticommute "by accident" even if it has them, like the Standard Model does.
I believe no one will understand what I wrote, but trust me that I was completely blown away when category theory turned a procedure that I always thought inelegant and brute-forced, and turned it into very clean concepts :)
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Warp wrote:
But why is this so? The only conclusion that I can draw is that even the original substitution trick was mathematically invalid, and it happened to give the correct answer by pure chance. There doesn't seem to be any obvious reason why the trick would be valid when there's a 2 on the right-hand-side but not when there's a 3. (Although I suppose there may well be a mathematical reason for it, but it's certainly not obvious.)
blackpenredpen does explain it, there are part 1-4 videos on the description of his main video.
To keep it short, the algebraic trick is valid, once some hypothesis is satisfied. What you actually prove by doing the substitution is:
If for some value of x, the infinite power tower converges to 2, then x is equal to sqrt(2).
and
If for some value of x, the infinite power tower converges to 3, then x is equal to cube root of 3.
It turns out that the conditional is true in the first sentence, but false in the second. Note that the substitution is useful, because it reduces the problem of calculating it to proving that it exists, which is much simpler. It's very common when solving these problems to neglect proving the existence of a value that makes the series converge, but it's necessary, as the example form blackpenredpen shows, you run into paradoxes if you neglect it.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
I guess I don't count, because I looked at the solution analysis when you posted it :P
Anyway, I have an "abstract nonsense" exercise (which is just about bashing definitions until they fit, which is always a lot of fun!). I already put the definition of a category here, but I'll put it again, because this thread is way too long.
A category consists of a collection of objects, and for each pair of objects, a set of morphisms between them. The collection of objects of a category C is often denoted obj(C), but we will usually denote the collection also by C. If A,B are in C, then the set of morphisms from A to B is denoted Mor(A,B).
Morphisms compose as expected. If f is in Mor(A,B) and g is in Mor(B,C), there is a morphism g o f in Mor(A,C). Composition is associative. For each object A in C, there is the identity morphism idA: A -> A, such that every morphism that's composed with it, either left or right, returns the same morphism. A morphism f is called an isomorphism if there is a (necessarily unique) morphism g such that both f o g and g o f are the identity morphism.
Questions:
(a) A category where every morphism is an isomorphism is called a groupoid. A perverse definition of a group is: a groupoid with a single object. Make sense of this.
(b) Give an example of a groupoid that's not a group.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
It's more or less along these lines, but there are more optimizations, that you are unlikely to see unless you keep submitting the problem.
I actually solved the equation X^N + Y^N = 1, reducing the problem to whether there are two N-th powers that sum to p+1. Finding two consecutive powers works just as fine.
As mentioned, since the map a -> a^n is essentially "random", we expect to find powers that satisfy with complexity O(sqrt(p)), as opposed to O(p). This map can also be efficiently computed by exponentiation by squaring.
However, there's still a catch. It's not hard to prove (use the fact that the multiplicative group of a field of prime size has a primitive root) that the image of the endomorphism a -> a^n has size (p-1)/gcd(n,p-1).
Because of this, the judge can make it very unlikely for us to find a solution by sending an n which shares lots of common factors with p-1. That way, the set will be very small, and you'll have to scan a large portion of the residues to find a solution, if one exists at all.
The solution to this is simple. Keep track of the size of the set of n-th power residues. If, at any point, you reach (p-1)/gcd(n,p-1), give up and say it's impossible.
I found this solution pretty neat when I found it. There are two cases: (1) the image of the endomorphism is large and we are very likely to find a solution in O(sqrt(p)) because of "randomness", (2) the image of the endomorphism is small, and we are very likely to find all its elements in O(sqrt(p)), again because of randomness.
It should also be pointed out that a -> a^n is not "random" if n = 1 mod (p-1), since by Fermat's Little Theorem, it's just the identity map. But this case is trivial and we can simply write down a solution.
DM me if you want the exact code (I don't want to post it on the Internet so anyone can submit it and get the problem), but the idea is:
if p is 2, output impossible
if p is not two, but n = 1 mod (p-1), output 1 1 2
declare a map m
for all numbers k, from 1 to p-1:
compute a <- k^n
set m[a] = k
if (m[p-1-a] is not null) output m[a], m[p-1-a], 1 and break
if (m.size = (p-1)/gcd(n,p-1)), output impossible and break
The implementation of the map has to be very efficient, because of the tight time limit. If you're using C++, it's just knowing which functions to call to make it run fast.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
r57shell mentioned competitive programming problems. Recently I saw one that's very interesting: https://codeforces.com/problemsets/acmsguru/problem/99999/511
Essentially, write an efficient computer program that finds a solution to a Fermat's Last Theorem-like equation for a field of prime characteristic. The prime and exponent can be as large as 1 million, and the program should run in 750 ms.
I am pretty confident I found the solution, but until now, I only had time to code a solution in Kotlin, using functional style so that I could do it fast. Unfortunately, it used way too much memory and I got Time Limit Exceeded. I'll try to write a solution in C++ to see if I can get it to pass.
Meanwhile, think about the problem!
EDIT: Got AC, the time limit is very tight, and I had to optimize, so it's a programming problem just as it is a math one!
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
r57shell wrote:
Second misunderstanding is, actually more precise knowledge of previous one. I need only two examples: f(x) = 1 only at x = zero, and everywhere else is 0 is
also fit requirements.
That's not true. For non-zero x, f(x-x)=f(x)f(-x). For this f, this would imply 1=0, so this function does not work.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Consider the location where the Korok Seeds are, and draw circles having these points as center, whose radius is the distance the masks can detect the seeds.
Seeing the problem this way, we want to minimize the number of circles, all of them with a given radius, where the outer points in the grid are inside the circles, and the center point outside.
Can we do it with one circle? Clearly not, a circle is a convex shape. If it contains two points, it contains the entire line connecting them. In particular, if it contains the two diagonal points in the grid, it contains the center one. Therefore, it's impossible to do it with one.
So, if we can find a construction with two circles, then it's the minimum. This can be done as follows. Consider two leaves that "form an L". If we imagine the bottom-left one as the origin of an xy axes system (0,0), we pair it with the leaf at (2,1). We can construct a circle containing leaves (0,0), (1,0), (2,0) and (2,1), but not the (1,1) point.
For this, construct a line segment between (0,0) and (2,1) and find its midpoint. From this midpoint, construct a perpendicular line going to the bottom right corner. If we define a point on this line sufficiently far, we can define a circle passing through (0,0) and (2,1) that will contain (1,0) and (2,0) but not (1,1).
We can repeat the same construction for leaves (0,1) and (2,2) and thus find two circles with the same radius covering the eight leaves, and only them. Therefore, the minimum number of seeds detected is 2.
---------------------
Consider a non-constant function f: R -> R satisfying:
f(x+y) = f(x)f(y),
for all real x and y.
Mark as true or false:
(1) f(x) is not even.
(2) f(0) = 1
(3) f(x) > 0 for all x in R
(4) f(x) is an exponential function
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
I remember you asking something along these lines about the sine function. In essence, your observation is correct. The logarithm function we all see in high school is defined from the set of positive real numbers to the set of real numbers.
In view of this, it's already wrong to even write ln(-2), because -2 is not in the domain, and the final result makes no sense either. He gives an infinite sequence of complex numbers, when the answer should be a single real number. From this (narrow) point of view, his result is not just wrong, it simply does not "compile". If a sentence like that comes up in a test, for example, by all means mark it as wrong.
However, this kinda misses the point. In the real world, mathematicians need to generalize things, in the hope that these will help them solve harder problems. It's a somewhat speculative endeavor, no one knows if a new concept will help solve tough problems, if we did we would already have solved them!
You should understand this video as "can we generalize the logarithm so that it makes sense to evaluate it at negative numbers?". The answer is yes, but there's not an unique way (in fact, in math you can generalize pretty much everything in a non-unique way, or else it wouldn't be a generalization xD)
I could also claim ln(-2)=ln(2). Notice that ln(1) = ln(-1)+ln(-1), which gives ln(-1)=0. So, ln(-2)=ln(2)+ln(-1)=ln(2)
Unjustified algebra arguments were a favorite of Euler. They are strictly speaking wrong, but they often lead to deep ideas. When blackpenredpen writes the distributive law of the logarithm for negative numbers, he's in fact making a political statement. He believes this law to be so important, that his generalized logarithm should obey it, or even be defined by it.
In modern terms, he's thinking of the logarithm as a homomorphism that should preserve some operations in a prescribed manner. And it turns out that, defined this way, it can be made rigorous. His logarithm is perfectly well defined as a homomorphism that takes the set of non-negative real numbers to the complex plane (where numbers that differ by a multiple of 2pi*i should be considered equal) and maps the multiplication on the reals to addition in the complex numbers.
In category theory, the whole syntax of the definitions is made to allow these kinds of arguments to be carried out rigorously with ease. There's a famous manifesto which is pretty accessible to computer scientists that introduces this kind of reasoning.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Next one! Prove that
P.S.: I recently came across this video sketching the proof of the Banach-Tarski paradox. It's much simpler than I thought it was, very similar to the construction used in the Grand Hotel paradox.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
FractalFusion wrote:
p4wn3r wrote:
For higher n, even showing that the number exists is quite a challenge. The standard proof invokes Schur's theorem.
Can't you just use induction on n to prove it?
If you want to approach the problem elementarily, yes, but it does get a bit messy when you write down the bound. The elementary induction approach is given here, in Proposition 2.1. Well, at least I think it's hard to write down the bound, others may find it easier. Anyway, the bound you get from that is horrible.
The same text proves it using Schur's theorem in Proposition 2.2, where the bound is better, but still not that great. For the McNugget problem (6, 9, 20), it gives 5*19=95, when the actual value is 44, less than its half.
Anyway, I'm not that interested in the elementary approach. By using generating functions, Schur's theorem arises quite naturally by looking at the multiplicity of the poles. See page 98 here. From this, it's quite simple to prove the existence using Schur's theorem directly.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Nice! Cut the knot also gives a proof based on generating functions. You can actually find everything that AoPS derives directly, by looking at the values of the polynomial at x=1 and x=-1, although you do need to apply l'Hopital to actually evaluate them.
Anyway, about its generalizations for higher n, for n=3, people have found a closed "formula" (if you can call it that) that's usually to messy to write down. For higher n, even showing that the number exists is quite a challenge. The standard proof invokes Schur's theorem. However, there's a very elegant proof using sheaf cohomology, which is how I came to be interested on it. This time, however, the complicated stuff is helpful and it actually improves the elementary solution quite a bit, It turns out that one can construct the proof using Castelnuovo-Mumford regularity and actually prove a bound for the Frobenius number.
This is very unusual. Usually homological/category-theoretical methods are highly non-constructive and provide no insight into elementary problems. For this one, however, it seems to be the only approach that yields a useful result!
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
In a previous post, I mentioned the following result:
If a and b are two positive integers, with gcd(a,b)=1, then the set
S = {ma+nb | m,n integers in Z} = Z
However, if we constrain m and n to be non-negative integers, it's in general not true that the set will be {0, 1, 2, ...}. For this case, however, we still can say something. Namely, if we define f(a,b) the largest integer not expressible by the form ma+nb (or, as a mathematician would say, a linear combination with non-negative integer coefficients), we have:
For any integers a, b greater than 1 such that gcd(a,b)=1, f(a,b) = ab-a-b
Prove this.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
I always get a lot of nostalgia seeing these. Some time ago this video popped up in my recommended on YouTube. I remember very well ten years ago. Lua scripting on emulators was just starting, and it was unthinkable to imagine you would need to know assembly to TAS at a high level. Nowadays, it's very common and I'm very happy that it's starting to get into popular culture, I have heard on several e-sports commentary memes regarding speedruns tending to skip the entire game.
One of the most amazing days I had was when the first Yellow ACE playaround appeared, and it shot up to front page on Hacker News, they were nice enough to cite one of my runs, which had my real name there, and several of my colleagues came into contact asking how we find these things out xD
I find it amazing that after a lot of time runs like these continue to inspire people. Yes vote.
Now, for the problems. It might help to represent diagrams for natural transformations in the style of the Wikipedia article:
(1) If we have two natural transformations n: F -> G and m: G -> H, where F,G,H: C -> D (that is, all of them are functors from category C to category D), show that we can compose them, and that composition has the structure of a monoid (it's associative and has an identity). This is the so-called vertical composition of natural transformations.
(2) If we have a natural transformation a: F -> G, where F, G: C->D, and a functor H: D -> E, show that we can find a natural transformation from H o F to H o G, called the right whiskering of a with respect to H.
(3) Similarly, show that if we have a natural transformation b: G -> H, where G,H: D -> E, and a functor F: C -> D, show that we can find a natural transformation from G o F to H o F, called the left whiskering of b with respect to F.
(4) Finally, if we have two natural transformations a: F-> G and b: H -> K, where F,G : C -> D and H,K: D-> E, show that we can define the horizontal composition b o a : H o F -> K o G in two ways:
(a) Left whiskering followed by right whiskering
(b) Right whiskering followed by left whiskering
Also, show that the definitions (a) and (b) define the same natural transformation.
Bonus: why are they called vertical and horizontal composition?for |α| > 1