5. Calculus problems
Example 14. (SMMC 2025 A1) A function $f: [0,\infty)\to [0,\infty)$ is max-poly if it is in the form of $f = \max (p_1,\ldots, p_n)$ where $p_i$ are real polynomials with $p_i (x) \geq 0$ for all $i = 1,\ldots , n$ and $x\geq 0$. Determine if $f = \min (x,x^2)$ is max-poly.
Remember how the growth rate of polynomials with distinct orders are completely separated? The same applies here. The growth rate of $f$ is $O(x)$ locking all polynomials to be of order at most 1 that the $x^2$ curve cannot form.
In fact, interpolation tells us that a segment from a polynomial cannot be a piecewise combination of other polynomials. That says we can prove the other way round. The $x^2$ curve forces at least one of the polynomial quadratic which would destroy the long term growth rate.
Example 15. (Putnam 2017 A3) Let $a<b$, $f,g:[a,b]\to (0,\infty)$ be continous with $\int ^b_a f(x)dx = \int ^b_a g(x)dx$ but $f\neq g$. Define $I_n = \int ^b_a (f(x)/g(x))^n \cdot f(x) dx$ for positive integers $n$. Show that $I_n$ is increasing and diverges to infinity.
Well the diverging part is clear knowing the whole thing is exponential right? Their integral being equal but the function being equal means there exists compact set $K$ of positive measure where $f(x) \geq (1+\delta)g(x)$. Let $m = \min _K f(x)$, then $I_n \geq m(1+\delta)^n \to \infty$.
Sure we need other tricks to help us dealing with the increasing part but that isn't too hard. Here I present something not used in official solution. If we extend definition to $I_0 = \int f(x)dx$ we can prove $I_1\geq I_0$ by direct calculation, then Hölder's inequality gives
$I_n = \int ^b_a \frac{f(x)^{n+1}}{g(x)^{n}} dx = \int ^b_a (\frac{f(x)^{n+2}}{g(x)^{n+1}})^{\frac{n}{n+1}}f(x)^{\frac{1}{n+1}} dx$
$\leq (\int ^b_a \frac{f(x)^{n+2}}{g(x)^{n+1}} dx )^{\frac{n}{n+1}} (\int ^b_a f(x)dx)^{\frac{1}{n+1}}$
But since $\int ^b_a f(x) dx = \int ^b_a g(x)dx$ that implies $I_n \leq I_{n+1}^{\frac{n}{n+1}}I_0^{\frac{1}{n+1}} \leq I_{n+1}^{\frac{n}{n+1}}I_n^{\frac{1}{n+1}}$
by induction, so $I_n\leq I_{n+1}$. Since $f\neq g$ strict inequality is achieved and we are done. The proof also indicates an exponential growth in long term.
Example 16. (Putnam 2009 B5) Let $f:(1,\infty)\to \mathbb{R}$ be differentiable with $f'(x) = \frac{x^2-f(x)^2}{x^2(f(x)^2+1)}$ for all $x>1$. Prove that $lim _{x\to \infty} f(x) = \infty$.
The derivative looks complicated but the core idea is that $f'(x)$ is slightly below 1 but not too far off, then it grows like $x$ which diverges to infinity. Qualitatively, we know $f'(x) = 1 - \frac{x^2+1}{x^2}\frac{f(x)^2}{1+f(x)^2}$. If $f(x)$ is bounded above then $f'$ is positive and bounded below which forces a contradiction.
The honorable mention here goes to 2010 A6 which like the above B6 will goes into exercise. The standard first solution looks horrible but think about the growth rate of that integral...
6. Generalization
From all the questions we have solved above, we see that growth rate sometimes act as a key step, sometimes plays a crucial role, but it's never the full solution. One would be silly to think this is all you need to master functional equation of similar problems.
That does not mean the understanding of growth rate ends here. Let us reconsider what growth rate brings us.
As example 10 exhibited, a polynomial growth rate is preserved, or characterized by powers. In other words, we are filtering other possibilities by looking for functions that satisfy the characterization, rather than calculating the growth rate.
Another way to characterize growth rate is of course eigenvectors. For example we know an exponential function is an eigenvector to frequency alteration $f(\cdot)\mapsto f(a\cdot)$ in the function space. In the same sense a monomial is an eigenvector to the dilation (scaling) operator. Instead of grinding hard on the growth rate, the implication itself could be more useful at times.
You may guess the keyword to be eigenvector which is not wrong but to me the more important takeaway is how you can understand growth rate as one of the filter which there are many more. Relate that to operators and you can see the problem in a much higher level.
This section is fully dedicated to a single problem which is arguably one of my top favourite contest problems:
Example 17. (SMMC 2025 A4) Let $V$ be a finite dimensional subspace of the space of smooth real functions. For every $f(x)\in V$, we have $f(2x)\in V$. Prove that $V$ only consists of polynomials.
There are two official solutions -- one generalized eigenvectors (what a pity they did not even mention this is generalized eigenvectors) and one by frequency filtering.
For the frequency filtering solution they quoted this lemma:
Lemma 3. Let $\theta _1, \ldots , \theta _m \in [0, 2\pi)$ be distinct angles, $h_1(x),\ldots, h_m(x)$ be polynomials (not necessarily real). Suppose the limit $\lim _{k\to \infty} \sum _{j=1}^m h_j(k) e^{ik\theta _j} = 0$
where limit is taken over integers $k$, then all $h_j$'s are zero.
The factor $e^{ik\theta _j}$ clearly screams Fourier which sparked me to think about a solution that truly utilize transformations. Unfortunately we would run into problems which we will address near the end. Yet, I still come up with an alternative solution of my taste as below.
The solution plays around the non-trivial linear relation $\sum c_jT^jf = 0$. Or rather, the whole solution is a repeated use (abuse) of it. In a pointwise version we write $f(x) = \sum c_i f(2^{-i}x)$.
We know that $f^{(k)}(0) = 0$ for all large enough $k$ as in all other solutions. This is by differentiating the linear combination $\sum c_jT^jf = 0$ and substitute $x = 0$ so get $f^{(k)}(0)\sum c_j 2^{kj} = 0$. For large enough $k$ the highest term dominates forcing the sum non-zero, hence $f^{(k)}(0)= 0$.
That says, $f$ has a finite Maclaurin polynomial $P$. Some other solution focuses on showing $f^{(k)}(x) = 0$ for other $x$, but we deal with the remainder $h = P-f$ instead.
Lemma 4. For any $f\in V$ the function is bounded by polynomial growth. More precisely, there exists a norm $ \|\cdot \|$ for $V$ and constants $C, \alpha >0$ such that $|f(x)| \leq C \| f\| |x|^{\alpha}$.
Proof. Let $M = \sup _{x\in [-1,1]}|f(x)|$ and consider the non-trivial linear recurrence $f(x) = \sum c_i f(2^{-i}x)$. Let $r = 1+\sum |c_i|$. Then induction gives $|f(x)| \leq r^nM$ for $|x| \in [2^{n-1},2^n]$, or simply that $|f(x)| \leq r^{1+\log _2 |x|} M$ which is a polynomial bound.
It is actually easier if we start with a norm although without knowing the polynomial bound it may not be trivial to pull out a norm other than the sup norm. Now we can use norms like $\|f\| = \int |f(x)|e^{-|x|}dx$. We can then have $C, \alpha >0$ that $\|Tf\| \leq c_1\|f\|$ and $\sup _{x\in [-1,1]}|f(x)| \leq c_2 \| f\|$. For $|x|\geq 1$ write $x = 2^ky$ where $|y|<1$ then $|f(x)| = |T^kf(y)| \leq c_1^k c_2 \|f\|$ which gives the same result.
The lemma implies that $h$ has at most polynomial growth at the far end. We combine with the fact that it shrinks faster than polynomial at zero as $h^{(k)}(0) = 0$ for all natural number $k$ to show that it is indeed zero.
Note that $h$ also satisfies the recurrence $h(x) = \sum c_i h(2^{-i}x)$. For large enough $k$ there exists $M_k$ such that $|h(x)| \leq M_k |x|^k$ for all $x$. Now we estimate
$\frac{|h(x)|}{|x|^k} \leq \sum (2^{-ik}|c_i| \frac{|h(2^{-i}x)|}{|2^{-i}x|^k}) \leq \sum (2^{-k}|c_i| \frac{|h(2^{-i}x)|}{|2^{-i}x|^k})$.
Taking supremum gives $M_k \leq M_k 2^{-k}\sum|c_i|$. We just need a large enough k where $2^{-k}\sum|c_i| <1$ to conclude $M_k = 0$. Essentially, a fixed dilation does not support nonzero remainder that decays faster than polynomial rate near zero. $\square$
I feel like this is a mix between the two official solutions which gives a clearer picture but meh.
Now back to our concern -- why can't we apply Fourier or Mellin transform and dig the frequency out of it? Usually technicalities like that would be left to readers but this is so fundamental that we shall get our hands dirty.
The major hurdle is the lack of guarantee that a smooth real function admits a Fourier transform (and converges over where it's useful). However, functions in the big space do not necessarily admit the transform does not mean we can't apply the transforms in the finite dimensional space $V$.
Lemma 4 is very powerful as it allows us to get a well-tamed remainder to work with. Adopt the notation $f = P+h$ and assume $h(x) = O(x^{\alpha})$.
The polynomial bound at both far end and at zero means the Mellin transform
$\mathcal{M}[h](s) = H(s) = \int ^{\infty}_0 h(x)x^{s-1}dx$
converges absolutely in the half plane $\textrm{Re}\,s < -\alpha$. It now suffices to look at the half plane.
The frequency doubling operator is easily transformed as $\mathcal{M}[T^jh](s) = 2^{-js}H(s)$, so $p(2^{-s})H(s) = 0$. Now pick a real number $\sigma < -\alpha$ that is on the left of all roots of $p$, i.e., $2^{-\sigma} > |z|$ for all $p(z) = 0$. Then $H(s) = 0$ on the vertical line $s = \sigma + i\zeta$ for real $\zeta$.
By writing $x = e^t$ we have
$H(\sigma + i\zeta) = \int _{\mathbb{R}} e^{\sigma t}h(e^t) e^{i\zeta t}dt = \int _{\mathbb{R}}u(t)e^{i\zeta t}dt$,
which we retrieved Fourier transform of some sort!
Absolute convergence says $u\in L^1(\mathbb{R})$ meaning this is a valid Fourier transformation on $u$. Since the transform is zero (not even distributional) we conclude that $u = 0$ and hence $h(x) = 0$ for $x>0$. Flip $h$ to repeat the argument then $h(x) = 0$ for $x<0$ then $h(0) = 0$ by continuity.
What differs from the my proposed solution is that we avoided the log-polynomial factors by limiting the reminder, and the technicalities allowed us to apply transformation where it had not been possible.
Something even more fascinating is how fascinatingly close our final trick of constructing a Fourier transform $\int _{\mathbb{R}}u(t)e^{i\zeta t}dt = 0$ to force zero looks almost the same as the lemma. They are of course child of two face, the discrete and continuous version of frequency filtering. There are so much more to talk about this, but I am afraid that such topic alone would be longer than this whole series and too hard to fit even the upper end of the taste here.
(Question - we used smoothness implicitly. Where did we use that? In particular, why do we need smoothness of infinite order? If you get stuck check the elementary solutions again.)
This question is one of my favourite in the sense it is a massive collaboration between advanced analysis and linear algebra but also allow specific branches like Fourier transform to kick in. There are so many perspectives you can look into, but each one of them is a generalization of growth rate tracing. I would even call this problem a major motivation to write this whole seminar.
7. Food for thoughts
Problems well worth mentioning but I was too lazy to fill them after all the work.
Problem 1. (Putnam 2022 B6) Find all functions $f:\mathbb{R}^+\to \mathbb{R}^+$ such that $f(xf(y)) + f(yf(x)) = 1 + f(x+y)$ for all $x,y>0$.
Problem 2. (SMMC 2021 B3) Find all real functions satifying the following two properties:
i) The Riemann integral $\int^b_a f(t)dt$ is well-defined for real $a<b$.
ii) For all real $x$ and positive integer $n$, $f(x) = \frac{n}{2}\int ^{x+1/n}_{x-1/n}f(t)dt$ holds.
Problem 3. (Putnam 2010 A6) Let $f:[0,\infty)\to \mathbb{R}$ be a strictly decreasing continuous function with $\lim _{x\to \infty}f(x) = 0$. Prove that $\int ^{\infty}_0 \frac{f(x)-f(x+1)}{f(x)}dx$ diverges.
Ask yourself -- what's the growth rate -- when you are stuck!!
No comments:
Post a Comment