1:29 Obviously based on the statement that f(1)² = f(1) has "a single solution 1" he's defining 0 to not be a Natural Number. But note that whether or not 0 is defined as a Natural Number is a matter of context, in set theory for instance 0 typically IS a Natural Number since the Natural Numbers are defined as the cardinalities of the finite sets (including the empty set which has cardinality 0). It might be an interesting aside to tweak the problem to include 0 and see what happens. Right off the bat, that opens up f(n) = 0 for various n as a possibility, for instance: -- f(0²) = f(0) = f(0)² implies f(0) = 1 or f(0) = 0 -- Likewise f(1) = 0 or 1 as well. Note also that f(1) = f(1² + 0²) = f(1)f(0) must also be either 1 or 0. So if f(0) = 0 then f(1) = 0 as well, and if f(0) = 1 then f(1) = 1 as well (they have to be identical)\ -- f(2) = f(1² + 1²) = f(1)f(1), so if f(1) = 1 then f(2) = 1 and likewise if f(1) = 0 then f(2) = 0. And so on. I'm out of time but my guess is if you follow the steps in the video, but assume f(0) = f(1) = 0 instead of being 1, you'll end up with the alternate solution f(n) = 0 for all n.
Let N₀ be the natural numbers including 0. Let f:N₀→N₀ satisfy the following two equations for all x and y in N₀: • f(x²+y²) = f(x)f(y), and • f(x²) = (f(x))². Consider x = 0. f(0) = f(0²) = (f(0))², so f(0) = 0 or 1. Now consider an arbitrary x. (f(x))² = f(x²) = f(x²+0²) = f(x)f(0). So, • if f(0) = 0, then for all x, (f(x))² = 0, so f(x) = 0, and • if f(0) = 1, then for all x, (f(x))² = f(x), so f(x) = 0 or 1. Clearly the following functions satisfy the functional equations: • f(n) = 0 for all n • f(n) = 1 for all n • f(0) = 1, f(n) = 0 for all n > 0 But do any other functions? Can f(n) = 1 for some but not all n > 0?
@@jeffcarey3045 That’s not generally true, like I said set theorists for example include 0 in the Natural Numbers because they’re defined as the cardinalities of the finite sets, and since the Empty Set has cardinality 0 that makes 0 the smallest Natural Number in that definition. Also the standard ISO/IEC 80000 includes 0 as a Natural Number as well. Likewise Peano’s Postulates include 0 as the first Natural Number On the other hand in Number Theory (which Penn’s videos deal with pretty often) 0 is not included because excluding 0 simplifies a lot of theorems in that setting. So there is actually no universal agreement on whether or not 0 is a Natural Number, it all depends on the context and who is defining it.
I did it the exact same way, but for a slight variant, you could use that for simple inductions it's often possible to do essentially the same reasoning, except assuming that there's a first violation of the induction, and then showing that that leads to a contradiction. So here, you'd ASSUME there's an f satisfying the problem that isn't identically 1. Then the set { f > 1 }, a subset of the naturals, isn't empty, and so by well ordering it has a least element n (i.e. f(n) > 1 and f(x) = 1 for 0 < x < n). Also, from f(1) = 1, have n > 1. If n is even, have n = 2m, and using x = 2m, y = 1, get f(4m^2 -1) f(n) = [ f(m) f(1) ]^2 = f(m)^2. But m < n, so f(m) = 1, so RHS = 1, but and f(n) > 1, and f(4m^2 -1) >= 1, so LHS > 1, a contradiction. Therefore n must be odd. Thus n = 2m+1 for some m > 0 (as n > 1), and (as in the video) using x = m+1, y = m, get f(n) f(2m^2 + 2m) = [ f(m) f(m+1) ]^2. The same reasoning as with the even case (and as with the video): since m and m+1 are both less than n, by the def of n have f(m) = f(m+1) = 1, and so RHS = 1, but LHS, which is f(n)>1 times a natural, is greater than 1, a contradiction. Thus the assumption was false and so f = 1 on the naturals is the only possible solution. A quick check shows that f = 1 is a solution, and so that proves that it's the only solution. As another tiny variant, since there's multiplication everywhere here, instead of showing a contradiction of one side > 1, other side = 1, you could use that a prime that divides n (since n > 1) must divide one side but not the other. That's possible, but not better (it's a bit worse... a touch more cumbersome than needed). However, in a different situation, such a divisibility observation might be the way to solve it. Anyway, the "work" of the proof is basically identical whether you're doing a positive induction like in the video, or a proof by contradiction which assumes that the induction fails at some point. (As a matter of style, I'd say that a positive induction is generally preferable over a proof by contradiction when possible. Induction also comes with the added benefit of proving that f = 1 actually is a solution, whereas using contradiction proves only that f = 1 is the only possible solution, but still might not be a solution.
(ac-bd)²+(ad+bc)²=(ac+bd)²+(ad-bc)², appling f and substituting b=c=1 we get: f(a-d)f(ad+1)=f(a+d)f(ad-1) If a,d≠1 ad+1>"the 3 other terms" So using strong induction and the preliminary base cases we get that f of every number n st. n-1≠p (prime) is 1 (because if n-1 is prime we need to have a=1 or d=1). So we know that f of every odd number is 1 Substituting b=c=1 and d=2 in the first equation we get: f(a-2)f(2a+1)=f(a+2)f(2a-1) Choosing a>2 and using strong induction we get that f(a+2)=1 completing the proof
I may not be right, but I see 2 problems in the proof. The first one is that maybe a or d may not be such that a-1 or d-1 are composit, and so the induction doesn't work; the second one is what happens when a=d (a-d=0). Still, that factorization is quite ingenious and I think you could somehow do a proof using it.
@@AntonioLasoGonzalez Thank you for your response: for the second problem I recognise a=d doesn't work, but we can easily fix this by noticing that f(a•a+1)=f(a)f(1) so using strong induction we get the same result (otherwise we can always change a and d so that a>d), for the first problem I'm not sure what you are referring to: my point is that if you set up the 3 inequalities ad+1>a+d, ad+1>a-d ad+1>ad-1 they are not respected only when a or d is 1, setting n=ad+1 there aren't a,d>1 st. ad=n-1 iff n-1 is prime. Also just for completness this identity comes from multipling (a²+b²)(c²+d²).
@@lucacastenetto1230 I think the problem is that maybe f(a+d) or f(ad-1) are not necessarily equal to one by the induction hypontesis. It may happen that (a+d)-1 is a prime number, for example, in which case the induction doesn't work. This is because your initial induction hypothesis is "For all n, if n-1 is not prime, then f(n)=1", and when appliying induction, you assume that this is the case for a+d and ad-1, which may be wrong because these numbers could possibly not satisfy the criteria to be included in the induction hypothesis.
I found that same first solution you presented. For your second solution strat, I think there's a couple problems. First, I don't think we can choose a and b in such a way that they are guaranteed to be smaller than n (in order to invoke strong induction). Secondly, even if you could, it would only prove it for sufficiently large n. This is because to guarantee multiple representations of n^2+m^2 as a sum of two squares, it needs to be composite (see Euler's Factorization Method). This depends on when the totient function of n exceeds the prime counting function of n, in order to guarantee such an m exists (by pigeonhole). Specifically, we want T(n)>pi(n)-w(n), where T is the totient function, and w is the number of distinct prime factors of n. Seeing that T(n)>pi(n)-w(n) even for something like n=24, it might not be impossible to prove it this way, but it's still not really necessary.
The same holds if we replace the codomain by R instead of N. Indeed, let’s prove by induction that, for each n in N, there is an integer exponent a(n) such that f(n)=f(1)^(a(n)) The proof of this fact for n = 3 and f(a-4)f(2a+2) = f(a+4)f(2a-2) whenever a >= 5, the claim follows for n = 2a+1 by using the first identity, and for n = 2a+2 using the second. Now, since f(1) = 1, the result follows, i.e., f is constant
I think if you allow 0 in the codomain then f(1)=0 is a possibility, and then I don't think it's so easy (or even possible maybe) to prove the result. In fact, I don't see how you could even prove that f(3)=0 in this case.
Great video as always! I thought about another approach: f(x^2+0^2)=f(x)*f(0)=f(x)*f(x) => f(x) = 0 or f(x) = f(0). f(x) = 0 is a solution, now consider f(x) = f(0). but f(0) = f(0)^2 => f(0) = 0 or f(0) = 1. but f(x) is not identically 0 so f(x) = 1. To sum up, f(x) is either identically 0 or 1.
Let y=0 in 1st equation: we get f(x^2)=f(x)*f(0), and by second equation, we get f(x^2)=(f(x))^2 So, f(x)*f(x)=f(x)*f(0), so either f(x)=0 or f(x)=f(0)=1, and for natural numbers, the only solution would be f(x)=1, isnt this a very small correct solution?
For the record: if N (the natural numbers) includes 0 - and that's how I was educated long time ago, but maybe it's also a regional question, I'm german - the problem is really trivial, you can directly conclude that f(x) = 1 is the only solution by setting y to 0 and checking the consequences. But what I wonder: are there maybe any smart theorems concerning such "domain switches" that could be used? In the sense of "if a functional equation applied to the non-negative integers has only one specific solution, those are the requirements that the same equation applied to the positive integers can have other solutions"?
Actually f(x) = 1 isn’t the only solution when 0 is included in the domain. For instance, f(x) = 0 works as well. Also I think f(x) = {1 if x=0, 0 otherwise} appears to work as well.
Reminds me of what I heard is supposedly the hardest problem they ever did on the german Bundeswettbewerb Mathematik: Given a recursive function f(0)=0, f(n)=n-f(f(n-1)), find an explicit formula for f(n)
I do remember the rough form of the solution - it was just floor(n/c) for a fitting constant c - though the way to get there was quite complicated (and I'll keep the value of c to myself for now - though if you try out a few values for n, you can probably guess it)@@maui9512
I solved this problem a bit differently. First, I let x be free and y=0. Thus, f(x^2)=f(x)f(0). Then, I applied the second function, making (f(x))^2=f(x)f(0). I checked if f(0) was a solution, which it was, so, with the addition of f(x)=0 to the solution set, I could divide both sides by f(x). Third, I divided both sides by f(x), giving f(x)=f(0). As the function is from the natural numbers to the natural numbers, f(0) is a natural number, so f(x)=n, where n is a natural number. Plugging this into the second equation, the only solution is f(x)=1. With the addition of f(x)=0, the only 2 solutions are f(x)=1, f(x)=0
A functional equation is just an equation (an expression with an equals sign and an unknown/s) where instead of the unknown/s being a number/s it is a function/s. For example any differential equation is a functional equation. The thing that makes functional equations "nasty" and only really solvable using ad-hoc methods is that they can involve function composition; linear ordinary differential equations don't involve function composition -- they contain only f(x), f'(x), f''(x), etc., never f(2x), f(x+1), f(x^2 + e^x), etc. -- and one can develop a general method for solving them (it turns out that solving a linear ODE just comes down to solving a polynomial equation), but functional equations allowing function composition makes them resistant to attack in general, because there just don't seem to exist good tools in mathematics for dealing with function composition. For example the Collatz conjecture is about function iteration which is the very special case of function composition of x, f(x), f(f(x)), f(f(f(x))), etc. and mathematicians are still hopelessly at a loss for a proof.
Yes! Let g(x) = log(f(x)). Then g(x+y) = log(f(x+y)) = log(f(x^{1/2})) + log(f(y^{1/2})) = (log(f(x)) + log(f(y)))/2 = (g(x) + g(y))/2. But f(0) = 1 by the second condition, so taking y =0 implies g(x) = 0 for all x in R.
The same holds if we replace R by R_+: notice that the g above satisfies g = 0 when restricted to Q. Then take x=x, y = k-x, k > x integer, and x \mapsto k-x, y = m + x, m positive integer. We obtain g(x) = g(m+x), whenever m is an integer. But g(x) + g(m+x) = 2 g(2x + m) = g(2x) + g(m) = g(x) + g(m) = g(x). Thus g(m+x) = 0 = g(x), for all x >0.
My curiosities are twofold: 1) what if we only have 1st eq? We have f(2 x^2) = f(x)^2 naturally from 1st eq, but the 2nd eq is actually a bit offseted as f(x^2), which leads to a strong relation f(x^2) = f(2x^2). What if we "fix" the 2nd eq to f(2x^2) = f(x)^2, which is more consistent with the 1st eq? 2) what if the codomain is broader, for example positive real numbers?
1) Fixing the 2ns eq to something that is a consequence of the 1st, is just dropping the 2nd eq. Let's explore: f(2)=f(1)²; f(5)=f(1)f(2)=f(1)³; f(1)f(7)=f(50)=f(5)²=f(1)^6², so f(7)=f(1)^5, ... -- but it seems hard to actually pin down the value f(1). One probably has to use more nice primes than just 2 and 5, but the next one is 13 = 2²+3². Does f(13)² = f(338) = f(5)f(12) help? I'm not sure. 2) Any positive real is the square of a positive real, hence for given x,y, let u=sqrt(x), v=sqrt(y) and find f(x² + y²) = f(x)f(y) = f(u²)f(v²) = f(u)²f(v)² = (f(u)f(v))² = f(u²+v²)² = f(x+y)². Now let y = 2a-x: f(x²+(2a-x)³) = f(2a)² does not depend on x. As x varies from 0 (excl.) to a (incl.), then x²+(2a-x)² varies from 4a² (excl.) down to 2a² (incl.). Then f is constant on any interval of the form [b,2b) (just let b = sqrt(a/2)). It follows that f is constant on the positive reals, say f(x) = c. But then c = f(17²+42²) = f(17)f(42) = c², so c=1. [EDIT: Oops, I just noticed that I broadened both domain and codomain]
What is the name given to functions with this property? f(c*x) = c*f(x) for any constant, c. Only example I can think of is f(x) = s*x where s is the coefficient, but I need a name for this class of function for computer science purposes.
Note, there are algorithmic functions that also have this property which is why I'm eager to find a name for them. Other examples of functions that could be part of the same class or related classes: c*f(x, y)=c*f(x, c*y), c*f(x, y)=f(c*x, c*y), c*f(x,y,z)=f(c*x,y,z), etc.
First condition, setting x=y, then f(2x²) = f²(x). Replacing RHS with Second condition leaves us f(2x²) = f(x²) which is only solved by "f(x) = const" (any const) as the only solution for first condtion. The second condtion limits this to const=1 and const=0 (if you consider 0 in N), because f=f².
hmmm constant functions are not the only solution to f(2x²) = f(x²), for example just consider a f(n) = n/2^(v_2(n)) this verifies the condition f(2n) = f(n) and so f(2x^2) = f(x^2)
That condition only affects squares. It could be that f(x^2) = constant but f(non square) = something else. But also you didn't really prove that constants are the only solution even for square numbers, indeed even that part isn't true. For example we could have f(x) = { k if x = k^2 or x = 2k^2, and x otherwise }
@@papesldjnsjkfjsnWhat is "v_2(n)"? But, any way, you have a fraction in your function (n/2), but the function to be looked for was to be in the natural numbers. If n is odd then this is no natural number anymore.
@@TheEternalVortex42 And how does this solve the problem? You can define any f(x) with new conditions inside. The task was to find explicit functions that hold true. This also works in your sense: f(x) = { all x in N that make the two requiered conditions true } Just introducing new "if"s and new undefined placeholder constants just shifts the problem to somewhere else without giving a solution.
@@johannmeier6707 v_2(n) is the 2-adic valuation, it is the highest "x" such that 2^x | n, and so if n is odd then v_2(n)=0 and 2^v_2(n) = 1, in particular n/(2^v_2(n)) is always an integer, this function works because it "ignores" the 2 factors kinda removes them so f(2^{anything}x) = f(x) and so it verifies your proprety
you realize that f(x+y) = f(sqrt(x)^2+sqrt(y)^2) = f(sqrt(x))f(sqrt(y)) We will also let y = 0 (this will not be in our domain, but we are just looking at more functions as solutions. The ones within our domain are a subset.) We see that f(x^2) = f(0)f(x) f(0+0) = f(0)f(0) = f(0)^2 f(0) = 0,1. If f(0) = 0, then f(x^2) = 0, therefore it cannot be our function. Let f(0) = 1, then f(x^2) = f(x). We can therefore say WLOG that f(sqrt(x)) = f(x). We have therefore shown that... f(x+y) = f(x)f(y). I am not going to solve this equation here, however you should see that either f(x) = 0, or f(x) = e^cx Obvious f(x) = 0 is not our function since 0 is not a natural number. We therefore know that f(x) = e^cx where c is any real number. We should naturally see that for this function to return only natural numbers, we need for c = 0. We therefore have that... f(x) = e^(0x) = 1 as our solution. We now need to show that there is no other solution for other c. This seems quite obvious, but I don't know how to prove this rigorously.
It is definitely not always possible. Just take the simplest case of n = 3. Then m is either 1 or 2, leading to possible square sums 3^2+1^2 = 10 or 3^2+2^2 = 13. However, if a and b are required to be less than n, they can only be 1s and 2s, so we can only have a^2+b^2 be 2, 5, or 8. Takes a little more work, but it also fails for the next number that cannot be expressed as the sum of two squares n=6. It does work for the next one n=7 since 7^2+1^2 = 50 = 5^2+5^2, but whether it will work for larger n values is up in the air.
@@burk314but even if there any counterexamples, wouldn’t that break the solution? I guess one can take care of the cases of n=3 and 6 separately and it will still work but one would then have to prove his claimed result
@@Happy_Abe Yes, the counterexamples do disprove the statement "If n cannot be expressed as a sum of two squares then there exist m, a, b < n such that n^2+m^2 = a^2+b^2". However, my point was that it may be possible to modify the statement to something like "If n>6 cannot....". As far as the solution goes, we would just have to deal with n=3 and 6 separately from all other n from his case 2.
I think there is a shorter way to solve this. If we take y=0, we get f(x^2+0^2)=f(0)f(x)=f(x^2)=f(x)^2. Therefore f(x)=0 or f(x)=f(0) for all x The second equation tells us that the value of f(0) is 0 or 1.
Isn’t f = 1 (and f=0) the trivial answer to the question? I expected that the difficulty comes from showing there aren’t any other function satisfying the requirements. And maybe I didn’t understand it but I don’t see you showing there can’t be any other functions.
Then if you took N to be {1,2,3,4,...}, f could not have a value of 0. A definition of N to be the positive integers in quite common; however, some like to include 0. As a mathematician, I've seen it done both ways but not in the same problem.
all he was doing is prooving that there aren't other answers you just didnt understand, he prooved by induction that f(n) = 1, that is to say the only possible value for f(n) is 1 so other functions can't exist
@@AntonioLasoGonzalez FYI the commenter above is using the definition of the Naturals that includes 0, while Penn in the video is using the definition where 0 is not a Natural Number. It’s two different definitions, both are common and whether or not 0 is treated as a Natural Number depends on the context.
Forget the Millennium problems, he'd get _really_ rich off his polynomial time Traveling Salesman algorithm. Also... Godel might have something to say about this.
![The most beautiful equation in math, explained visually [Euler’s Formula]](http://i.ytimg.com/vi/f8CXG7dS-D0/mqdefault.jpg)
Why is half the comments debating if whether 0 should be included in |N LOL
Who else looked at this and thought huh, f(2x²) = f(x²)?
yes, that's why the fubction must be f(x) = 1
1:29 Obviously based on the statement that f(1)² = f(1) has "a single solution 1" he's defining 0 to not be a Natural Number. But note that whether or not 0 is defined as a Natural Number is a matter of context, in set theory for instance 0 typically IS a Natural Number since the Natural Numbers are defined as the cardinalities of the finite sets (including the empty set which has cardinality 0).
It might be an interesting aside to tweak the problem to include 0 and see what happens. Right off the bat, that opens up f(n) = 0 for various n as a possibility, for instance:
-- f(0²) = f(0) = f(0)² implies f(0) = 1 or f(0) = 0
-- Likewise f(1) = 0 or 1 as well. Note also that f(1) = f(1² + 0²) = f(1)f(0) must also be either 1 or 0. So if f(0) = 0 then f(1) = 0 as well, and if f(0) = 1 then f(1) = 1 as well (they have to be identical)\
-- f(2) = f(1² + 1²) = f(1)f(1), so if f(1) = 1 then f(2) = 1 and likewise if f(1) = 0 then f(2) = 0.
And so on. I'm out of time but my guess is if you follow the steps in the video, but assume f(0) = f(1) = 0 instead of being 1, you'll end up with the alternate solution f(n) = 0 for all n.
Am I missing something, or would f(0)=1, f(n)=0 for all other n work as well?
@@emilyliedtke7059 Actually you’re right, f(0) = 1 and f(1) = 0 seems consistent too.
W is the set that contains 0. N does not contain 0.
Let N₀ be the natural numbers including 0. Let f:N₀→N₀ satisfy the following two equations for all x and y in N₀:
• f(x²+y²) = f(x)f(y), and
• f(x²) = (f(x))².
Consider x = 0. f(0) = f(0²) = (f(0))², so f(0) = 0 or 1.
Now consider an arbitrary x. (f(x))² = f(x²) = f(x²+0²) = f(x)f(0). So,
• if f(0) = 0, then for all x, (f(x))² = 0, so f(x) = 0, and
• if f(0) = 1, then for all x, (f(x))² = f(x), so f(x) = 0 or 1.
Clearly the following functions satisfy the functional equations:
• f(n) = 0 for all n
• f(n) = 1 for all n
• f(0) = 1, f(n) = 0 for all n > 0
But do any other functions? Can f(n) = 1 for some but not all n > 0?
@@jeffcarey3045 That’s not generally true, like I said set theorists for example include 0 in the Natural Numbers because they’re defined as the cardinalities of the finite sets, and since the Empty Set has cardinality 0 that makes 0 the smallest Natural Number in that definition. Also the standard ISO/IEC 80000 includes 0 as a Natural Number as well. Likewise Peano’s Postulates include 0 as the first Natural Number
On the other hand in Number Theory (which Penn’s videos deal with pretty often) 0 is not included because excluding 0 simplifies a lot of theorems in that setting.
So there is actually no universal agreement on whether or not 0 is a Natural Number, it all depends on the context and who is defining it.
I did it the exact same way, but for a slight variant, you could use that for simple inductions it's often possible to do essentially the same reasoning, except assuming that there's a first violation of the induction, and then showing that that leads to a contradiction.
So here, you'd ASSUME there's an f satisfying the problem that isn't identically 1.
Then the set { f > 1 }, a subset of the naturals, isn't empty, and so by well ordering it has a least element n (i.e. f(n) > 1 and f(x) = 1 for 0 < x < n). Also, from f(1) = 1, have n > 1.
If n is even, have n = 2m, and using x = 2m, y = 1, get f(4m^2 -1) f(n) = [ f(m) f(1) ]^2 = f(m)^2. But m < n, so f(m) = 1, so RHS = 1, but and f(n) > 1, and f(4m^2 -1) >= 1, so LHS > 1, a contradiction.
Therefore n must be odd.
Thus n = 2m+1 for some m > 0 (as n > 1), and (as in the video) using x = m+1, y = m, get
f(n) f(2m^2 + 2m) = [ f(m) f(m+1) ]^2.
The same reasoning as with the even case (and as with the video): since m and m+1 are both less than n, by the def of n have f(m) = f(m+1) = 1, and so RHS = 1, but LHS, which is f(n)>1 times a natural, is greater than 1, a contradiction.
Thus the assumption was false and so f = 1 on the naturals is the only possible solution.
A quick check shows that f = 1 is a solution, and so that proves that it's the only solution.
As another tiny variant, since there's multiplication everywhere here, instead of showing a contradiction of one side > 1, other side = 1, you could use that a prime that divides n (since n > 1) must divide one side but not the other. That's possible, but not better (it's a bit worse... a touch more cumbersome than needed). However, in a different situation, such a divisibility observation might be the way to solve it.
Anyway, the "work" of the proof is basically identical whether you're doing a positive induction like in the video, or a proof by contradiction which assumes that the induction fails at some point. (As a matter of style, I'd say that a positive induction is generally preferable over a proof by contradiction when possible. Induction also comes with the added benefit of proving that f = 1 actually is a solution, whereas using contradiction proves only that f = 1 is the only possible solution, but still might not be a solution.
(ac-bd)²+(ad+bc)²=(ac+bd)²+(ad-bc)², appling f and substituting b=c=1 we get:
f(a-d)f(ad+1)=f(a+d)f(ad-1)
If a,d≠1 ad+1>"the 3 other terms"
So using strong induction and the preliminary base cases we get that f of every number n st. n-1≠p (prime) is 1 (because if n-1 is prime we need to have a=1 or d=1).
So we know that f of every odd number is 1
Substituting b=c=1 and d=2 in the first equation we get:
f(a-2)f(2a+1)=f(a+2)f(2a-1)
Choosing a>2 and using strong induction we get that f(a+2)=1 completing the proof
I may not be right, but I see 2 problems in the proof. The first one is that maybe a or d may not be such that a-1 or d-1 are composit, and so the induction doesn't work; the second one is what happens when a=d (a-d=0). Still, that factorization is quite ingenious and I think you could somehow do a proof using it.
@@AntonioLasoGonzalez Thank you for your response: for the second problem I recognise a=d doesn't work, but we can easily fix this by noticing that f(a•a+1)=f(a)f(1) so using strong induction we get the same result (otherwise we can always change a and d so that a>d), for the first problem I'm not sure what you are referring to: my point is that if you set up the 3 inequalities ad+1>a+d, ad+1>a-d ad+1>ad-1 they are not respected only when a or d is 1, setting n=ad+1
there aren't a,d>1 st. ad=n-1 iff n-1 is prime.
Also just for completness this identity comes from multipling (a²+b²)(c²+d²).
@@lucacastenetto1230 I think the problem is that maybe f(a+d) or f(ad-1) are not necessarily equal to one by the induction hypontesis. It may happen that (a+d)-1 is a prime number, for example, in which case the induction doesn't work. This is because your initial induction hypothesis is "For all n, if n-1 is not prime, then f(n)=1", and when appliying induction, you assume that this is the case for a+d and ad-1, which may be wrong because these numbers could possibly not satisfy the criteria to be included in the induction hypothesis.
Excluding 0 from N should be declared. It's convention among English speaking countries but not much of the others.
I found that same first solution you presented. For your second solution strat, I think there's a couple problems.
First, I don't think we can choose a and b in such a way that they are guaranteed to be smaller than n (in order to invoke strong induction). Secondly, even if you could, it would only prove it for sufficiently large n. This is because to guarantee multiple representations of n^2+m^2 as a sum of two squares, it needs to be composite (see Euler's Factorization Method). This depends on when the totient function of n exceeds the prime counting function of n, in order to guarantee such an m exists (by pigeonhole). Specifically, we want T(n)>pi(n)-w(n), where T is the totient function, and w is the number of distinct prime factors of n.
Seeing that T(n)>pi(n)-w(n) even for something like n=24, it might not be impossible to prove it this way, but it's still not really necessary.
16:15 check is a one-liner: n = 2m + 1 = m + (m + 1), where both summands are at least 1.
The same holds if we replace the codomain by R instead of N.
Indeed, let’s prove by induction that, for each n in N, there is an integer exponent a(n) such that
f(n)=f(1)^(a(n))
The proof of this fact for n = 3 and f(a-4)f(2a+2) = f(a+4)f(2a-2) whenever a >= 5, the claim follows for n = 2a+1 by using the first identity, and for n = 2a+2 using the second.
Now, since f(1) = 1, the result follows, i.e., f is constant
I think if you allow 0 in the codomain then f(1)=0 is a possibility, and then I don't think it's so easy (or even possible maybe) to prove the result. In fact, I don't see how you could even prove that f(3)=0 in this case.
Great video as always! I thought about another approach:
f(x^2+0^2)=f(x)*f(0)=f(x)*f(x) => f(x) = 0 or f(x) = f(0).
f(x) = 0 is a solution, now consider f(x) = f(0).
but f(0) = f(0)^2 => f(0) = 0 or f(0) = 1.
but f(x) is not identically 0 so f(x) = 1.
To sum up, f(x) is either identically 0 or 1.
Let y=0 in 1st equation:
we get f(x^2)=f(x)*f(0), and by second equation, we get f(x^2)=(f(x))^2
So, f(x)*f(x)=f(x)*f(0), so either f(x)=0 or f(x)=f(0)=1, and for natural numbers, the only solution would be f(x)=1, isnt this a very small correct solution?
There's one word I like to say about this presentation: "NIFTY!!!"
16:50 The head of that arrow looks like a perfectly written capitalized V.
excellent problem
For the record: if N (the natural numbers) includes 0 - and that's how I was educated long time ago, but maybe it's also a regional question, I'm german - the problem is really trivial, you can directly conclude that f(x) = 1 is the only solution by setting y to 0 and checking the consequences. But what I wonder: are there maybe any smart theorems concerning such "domain switches" that could be used? In the sense of "if a functional equation applied to the non-negative integers has only one specific solution, those are the requirements that the same equation applied to the positive integers can have other solutions"?
Good old DIN 5473
Actually f(x) = 1 isn’t the only solution when 0 is included in the domain. For instance, f(x) = 0 works as well. Also I think f(x) = {1 if x=0, 0 otherwise} appears to work as well.
Reminds me of what I heard is supposedly the hardest problem they ever did on the german Bundeswettbewerb Mathematik: Given a recursive function f(0)=0, f(n)=n-f(f(n-1)), find an explicit formula for f(n)
Do you remember the solution
is it in N or Z?
In N (with 0, obviously), though now I'm wondering whether it would also work in Z @@papesldjnsjkfjsn
I do remember the rough form of the solution - it was just floor(n/c) for a fitting constant c - though the way to get there was quite complicated (and I'll keep the value of c to myself for now - though if you try out a few values for n, you can probably guess it)@@maui9512
Or maybe it was the ceiling function, one of the two
I solved this problem a bit differently. First, I let x be free and y=0. Thus, f(x^2)=f(x)f(0). Then, I applied the second function, making (f(x))^2=f(x)f(0). I checked if f(0) was a solution, which it was, so, with the addition of f(x)=0 to the solution set, I could divide both sides by f(x). Third, I divided both sides by f(x), giving f(x)=f(0). As the function is from the natural numbers to the natural numbers, f(0) is a natural number, so f(x)=n, where n is a natural number. Plugging this into the second equation, the only solution is f(x)=1. With the addition of f(x)=0, the only 2 solutions are f(x)=1, f(x)=0
Excluding 0 from ℕ is very confusing. I ended up resolving a completely different problem :o Using ℕ* or ℕ\{0} notation would be proper.
Or ℤ⁺
Depends on the math tradition. It would be very confusing for me if 0 was included.
0 not in ℕ is more common
We drink every time he says "one"....
1:36 0 is a natural number also satisfying that equation
0 is NOT a natural number.
In which of the play lists you have put this.?
Hey Michael, what kind of chalkboard do you use? I love the sound!
I bet is vintage Hagoromo or a brand derived from that.
Can you do a video on what a functional equation actually is?
Its just an equation where your x or y is replaced by f(x) or f(y). These function can be derivatives but also at x+y or 40-x^2. U make it
you have to find all function from some set to another (specified in the problem), which satifie all given conditions
A functional equation is just an equation (an expression with an equals sign and an unknown/s) where instead of the unknown/s being a number/s it is a function/s. For example any differential equation is a functional equation.
The thing that makes functional equations "nasty" and only really solvable using ad-hoc methods is that they can involve function composition; linear ordinary differential equations don't involve function composition -- they contain only f(x), f'(x), f''(x), etc., never f(2x), f(x+1), f(x^2 + e^x), etc. -- and one can develop a general method for solving them (it turns out that solving a linear ODE just comes down to solving a polynomial equation), but functional equations allowing function composition makes them resistant to attack in general, because there just don't seem to exist good tools in mathematics for dealing with function composition. For example the Collatz conjecture is about function iteration which is the very special case of function composition of x, f(x), f(f(x)), f(f(f(x))), etc. and mathematicians are still hopelessly at a loss for a proof.
@Michael: My friend Peano says 0 is a natural number.
Depends on the context, natural number may or may not include 0.
If we replace the f: N→N with f: R→R, can we still solve it?
Yes!
Let g(x) = log(f(x)). Then g(x+y) = log(f(x+y)) = log(f(x^{1/2})) + log(f(y^{1/2})) = (log(f(x)) + log(f(y)))/2 = (g(x) + g(y))/2.
But f(0) = 1 by the second condition, so taking y =0 implies g(x) = 0 for all x in R.
The same holds if we replace R by R_+: notice that the g above satisfies g = 0 when restricted to Q. Then take x=x, y = k-x, k > x integer, and x \mapsto k-x, y = m + x, m positive integer. We obtain g(x) = g(m+x), whenever m is an integer. But
g(x) + g(m+x) = 2 g(2x + m) = g(2x) + g(m) = g(x) + g(m) = g(x). Thus g(m+x) = 0 = g(x), for all x >0.
It's either the Function identical to 1 or 0.
If we count 0 as a natural number we get two possible answers in a matter if seconds.
r/unexpectedbatman
But then the problem would not be as interesting
Finding some answers in never really the interesting part. Proving you've found all the answers is
how did you find ALL POSSIBLE functions so quickly? It'd take me a few minutes at least!
@@egoreremeev9969 Why would it be less interesting with additional answers?
My curiosities are twofold:
1) what if we only have 1st eq?
We have f(2 x^2) = f(x)^2 naturally from 1st eq, but the 2nd eq is actually a bit offseted as f(x^2), which leads to a strong relation f(x^2) = f(2x^2). What if we "fix" the 2nd eq to f(2x^2) = f(x)^2, which is more consistent with the 1st eq?
2) what if the codomain is broader, for example positive real numbers?
1) Fixing the 2ns eq to something that is a consequence of the 1st, is just dropping the 2nd eq.
Let's explore: f(2)=f(1)²; f(5)=f(1)f(2)=f(1)³; f(1)f(7)=f(50)=f(5)²=f(1)^6², so f(7)=f(1)^5, ... -- but it seems hard to actually pin down the value f(1). One probably has to use more nice primes than just 2 and 5, but the next one is 13 = 2²+3². Does f(13)² = f(338) = f(5)f(12) help? I'm not sure.
2) Any positive real is the square of a positive real, hence for given x,y, let u=sqrt(x), v=sqrt(y) and find
f(x² + y²) = f(x)f(y) = f(u²)f(v²) = f(u)²f(v)² = (f(u)f(v))² = f(u²+v²)² = f(x+y)².
Now let y = 2a-x: f(x²+(2a-x)³) = f(2a)² does not depend on x. As x varies from 0 (excl.) to a (incl.), then x²+(2a-x)² varies from 4a² (excl.) down to 2a² (incl.). Then f is constant on any interval of the form [b,2b) (just let b = sqrt(a/2)). It follows that f is constant on the positive reals, say f(x) = c. But then c = f(17²+42²) = f(17)f(42) = c², so c=1.
[EDIT: Oops, I just noticed that I broadened both domain and codomain]
I have fan of functional equation till i red a polish best and only book in this field.
0 is a natural number. Anyone who says otherwise is mad
Depends on how the set of natural numbers is defined. The usage of different definitions seems to depend on the region.
0 is not a natural number. Ask any anthropologist. 0 was invented way later than the natural numbers.
Haven't watched the video yet but I did it by using the Pythagorean triples generator
Same solution except I used the sub g(x) = f(x) - 1
What is the name given to functions with this property? f(c*x) = c*f(x) for any constant, c.
Only example I can think of is f(x) = s*x where s is the coefficient, but I need a name for this class of function for computer science purposes.
Note, there are algorithmic functions that also have this property which is why I'm eager to find a name for them. Other examples of functions that could be part of the same class or related classes: c*f(x, y)=c*f(x, c*y), c*f(x, y)=f(c*x, c*y), c*f(x,y,z)=f(c*x,y,z), etc.
y=MX is like the only polynomial which satisfies such a relation
First condition, setting x=y, then f(2x²) = f²(x). Replacing RHS with Second condition leaves us f(2x²) = f(x²) which is only solved by "f(x) = const" (any const) as the only solution for first condtion. The second condtion limits this to const=1 and const=0 (if you consider 0 in N), because f=f².
hmmm constant functions are not the only solution to f(2x²) = f(x²), for example just consider a f(n) = n/2^(v_2(n)) this verifies the condition f(2n) = f(n) and so f(2x^2) = f(x^2)
That condition only affects squares. It could be that f(x^2) = constant but f(non square) = something else. But also you didn't really prove that constants are the only solution even for square numbers, indeed even that part isn't true. For example we could have f(x) = { k if x = k^2 or x = 2k^2, and x otherwise }
@@papesldjnsjkfjsnWhat is "v_2(n)"? But, any way, you have a fraction in your function (n/2), but the function to be looked for was to be in the natural numbers. If n is odd then this is no natural number anymore.
@@TheEternalVortex42 And how does this solve the problem? You can define any f(x) with new conditions inside. The task was to find explicit functions that hold true.
This also works in your sense:
f(x) = { all x in N that make the two requiered conditions true }
Just introducing new "if"s and new undefined placeholder constants just shifts the problem to somewhere else without giving a solution.
@@johannmeier6707 v_2(n) is the 2-adic valuation, it is the highest "x" such that 2^x | n, and so if n is odd then v_2(n)=0 and 2^v_2(n) = 1, in particular n/(2^v_2(n)) is always an integer, this function works because it "ignores" the 2 factors kinda removes them so f(2^{anything}x) = f(x) and so it verifies your proprety
you realize that f(x+y) = f(sqrt(x)^2+sqrt(y)^2) = f(sqrt(x))f(sqrt(y))
We will also let y = 0 (this will not be in our domain, but we are just looking at more functions as solutions. The ones within our domain are a subset.)
We see that f(x^2) = f(0)f(x)
f(0+0) = f(0)f(0) = f(0)^2
f(0) = 0,1.
If f(0) = 0, then f(x^2) = 0, therefore it cannot be our function.
Let f(0) = 1, then f(x^2) = f(x).
We can therefore say WLOG that f(sqrt(x)) = f(x).
We have therefore shown that...
f(x+y) = f(x)f(y).
I am not going to solve this equation here, however you should see that either f(x) = 0, or f(x) = e^cx
Obvious f(x) = 0 is not our function since 0 is not a natural number. We therefore know that f(x) = e^cx where c is any real number.
We should naturally see that for this function to return only natural numbers, we need for c = 0. We therefore have that...
f(x) = e^(0x) = 1 as our solution.
We now need to show that there is no other solution for other c. This seems quite obvious, but I don't know how to prove this rigorously.
Nice problem :)
@18:30 how would one show one can always represent a sum of squares as a different sum of squares with that property?
It is definitely not always possible. Just take the simplest case of n = 3. Then m is either 1 or 2, leading to possible square sums 3^2+1^2 = 10 or 3^2+2^2 = 13. However, if a and b are required to be less than n, they can only be 1s and 2s, so we can only have a^2+b^2 be 2, 5, or 8.
Takes a little more work, but it also fails for the next number that cannot be expressed as the sum of two squares n=6. It does work for the next one n=7 since 7^2+1^2 = 50 = 5^2+5^2, but whether it will work for larger n values is up in the air.
@@burk314so then his other idea of a solution is in fact not a solution at all?
@@Happy_Abe Maybe n=3 and 6 are the only exceptions and it always works after that, but even if it is true, there's a lot more work to do to prove it.
@@burk314but even if there any counterexamples, wouldn’t that break the solution?
I guess one can take care of the cases of n=3 and 6 separately and it will still work but one would then have to prove his claimed result
@@Happy_Abe Yes, the counterexamples do disprove the statement "If n cannot be expressed as a sum of two squares then there exist m, a, b < n such that n^2+m^2 = a^2+b^2". However, my point was that it may be possible to modify the statement to something like "If n>6 cannot....".
As far as the solution goes, we would just have to deal with n=3 and 6 separately from all other n from his case 2.
Why functional equations always have such boring answer, like constant or linear function..
You should be more rigorous about natural set you use it is often contains zero but obviously not in your case
I think there is a shorter way to solve this. If we take y=0, we get f(x^2+0^2)=f(0)f(x)=f(x^2)=f(x)^2.
Therefore f(x)=0 or f(x)=f(0) for all x
The second equation tells us that the value of f(0) is 0 or 1.
this is also my solution
0 is not on the domain of f.
Isn’t f = 1 (and f=0) the trivial answer to the question?
I expected that the difficulty comes from showing there aren’t any other function satisfying the requirements.
And maybe I didn’t understand it but I don’t see you showing there can’t be any other functions.
Then if you took N to be {1,2,3,4,...}, f could not have a value of 0. A definition of N to be the positive integers in quite common; however, some like to include 0. As a mathematician, I've seen it done both ways but not in the same problem.
The whole point of the proof is to show that f = 1 is the only solution
all he was doing is prooving that there aren't other answers you just didnt understand, he prooved by induction that f(n) = 1, that is to say the only possible value for f(n) is 1 so other functions can't exist
He proved that if f satisfies the conditions, then f(x)=1 for all natural numbers x. Proving the converse is trivial.
@@AntonioLasoGonzalez FYI the commenter above is using the definition of the Naturals that includes 0, while Penn in the video is using the definition where 0 is not a Natural Number. It’s two different definitions, both are common and whether or not 0 is treated as a Natural Number depends on the context.
Why the result of every functional problems is always constant or linear ? Boring.
I think the solutions both supposed that there is a function like that.
It's pretty obvious that f = 1 satisfies the conditions (but also this is proven by the induction argument anyway)
what?
It's obviously exponential functions. Cool tho
Sir
I beg u answer my question.
Is there a math problem u can't solve it?
The Riemann hypothesis, probably.
@@QuantSpazar Good one LoL 😂😂😂😂😂😂
Lord Daniel,
I beg you to use common sense 😭
No.
Forget the Millennium problems, he'd get _really_ rich off his polynomial time Traveling Salesman algorithm.
Also... Godel might have something to say about this.