55
$\begingroup$

This is a somewhat frivolous question, so I won't mind if it gets closed. One of the categories of Olympiad-style problems (e.g. at the IMO) is solving various functional equations, such as those given in this handout. While I can see the pedagogical value in doing a few of these problems, I never saw the point in practicing this particular type of problem much, and now that I'm a little older and wiser I still don't see anywhere that problems of this type appear in a major way in modern mathematics.

(There are a few notable exceptions, such as the functional equation defining modular forms, but the generic functional equation problem has much less structure than a group acting via a cocycle. I am talking about a contrived problem like finding all functions $f : \mathbb{R} \to \mathbb{R}$ satisfying

$$f(x f(x) + f(y)) = y + f(x)^2.$$

When would this condition ever appear in "real life"?!)

Is this impression accurate, or are there branches of mathematics where these kinds of problems actually appear? (I would be particularly interested if the condition, like the one above, involves function composition in a nontrivial way.)


Edit: Thank you everyone for all of your answers. As darij correctly points out in the comments, I haven't phrased the question specifically enough. I am aware that there is a lot of interesting mathematics that can be phrased as solving certain nice functional equations; the functional equations I wanted to ask about are specifically the really contrived ones like the one above. The implicit question being: "relative to other types of Olympiad problems, would it have been worth it to spend a lot of time solving functional equations?"

$\endgroup$
14
  • 4
    $\begingroup$ I'm ambivalent about your actual question, but I would strongly prefer it if you changed your title. Surely you can find an adjective other than "serious" to describe what you mean? $\endgroup$
    – Yemon Choi
    Jan 27, 2011 at 1:19
  • 5
    $\begingroup$ It's somewhat strange to exclude any example that involves a group action. If we've learned anything in the last century, it is that a majority of interesting mathematical structure that are worth considering are tied to the actions of groups (or group-like objects)... $\endgroup$
    – Terry Tao
    Jan 27, 2011 at 10:35
  • 6
    $\begingroup$ I think two questions should be distinguished here: (1) Does any research mathematics involve solving (nontrivial) functional equations (by any method whatsoever)? (2) Does any research mathematics involve the methods usually employed for olympiad-style elementary functional equations? While the answer to (1) is clearly a "yes" (differential equations, difference equations etc.), I believe the answer to (2) is a No in the sense that most methods I have learnt in my olympiad time are utterly useless to me now. Of course, some func. eqn. problems HAVE conceptual solutions (such as finding a ... $\endgroup$ Jan 27, 2011 at 10:48
  • 3
    $\begingroup$ ... hidden group action, exploiting a symmetry), but most of the tricks (substituting 0, 1, -1, x=y, etc.; exploiting monotony proving that functions are continuous; etc.) I have never seen used anywhere outside of func. eqns., except in two places: (a) proofs that some axioms of algebraic structures can be omitted (e. g., if I remember correctly, one can omit the commutativity of + in the definition of a field) and (b) the proof that any homomorphism between fields must be injective. While (a) can be research mathematics, it seems more like an art-pour-l'art to me, without any uses. (b) ... $\endgroup$ Jan 27, 2011 at 10:52
  • 3
    $\begingroup$ @darij: Great idea - when will the newspapers start including functional equations on their puzzle pages? $\endgroup$
    – ndkrempel
    Jan 27, 2011 at 15:24

14 Answers 14

46
$\begingroup$

In additive combinatorics, one often seeks to count patterns such as an arithmetic progression $a, a+r, \ldots, a+(k-1)r$. When doing so, one is naturally led to expressions such as $$ {\bf E}_{a,r \in G} f_0(a) f_1(a+r) \ldots f_{k-1}(a+(k-1)r)$$ for some finite abelian group $G$ and some complex-valued functions $f_0,\ldots,f_{k-1}$. If these functions are bounded in magnitude by $1$, then the above expression is also bounded in magnitude by one. When does equality hold? Precisely when one has a functional equation $$ f_0(a) f_1(a+r) \ldots f_{k-1}(a+(k-1)r) = c$$ for some constant $c$ of magnitude $1$. One can solve this functional equation, and discover that each $f_j$ must take the form $f_j(a) = e^{2\pi i P_j(a)}$ for some polynomial $P_j: G \to {\bf R}/{\bf Z}$ of degree at most $k-2$. This observation can be viewed as the starting point for the study of Gowers uniformity norms, and one can perform a similar analysis to start understanding many other patterns in additive combinatorics.

In ergodic theory, cocycle equations, of which the coboundary equation

$$ \rho(x) = F(T(x)) - F(x)$$

is the simplest example, play an important role in the study of extensions of dynamical systems and their cohomology. Despite the apparently algebraic nature of such equations, though, one often solves these equations instead by analytic means (and in particular, not by IMO techniques), for instance by using the spectral theory or mixing properties of the shift $T$, and exploiting the measurability or regularity properties of $\rho$ or $F$. (The solving of such equations, incidentally, is a crucial aspect of the ergodic theory analogue of the study of the Gowers uniformity norms mentioned earlier, as developed by Host-Kra and Ziegler.)

Returning to the more "contrived" functional equations of Olympiad type, note that such equations usually use (a) the additive structure of the domain and range, (b) the multiplicative structure of the domain and range, and (c) the fact that the domain and range are identical (so that one can perform compositions such as $f(f(x))$). In most mathematical subjects, at least one of these features is absent or irrelevant, which helps explain why such equations are relatively rare in research mathematics. For instance, in many branches of analysis, the range of functions (typically ${\bf R}$ or ${\bf C}$) usually has no natural reason to be identified with the domain of functions (which may ``accidentally'' be ${\bf R}$ or ${\bf C}$, but is often more naturally viewed in a more general category, such as that of measure spaces, topological spaces, or manifolds), so (c) is usually absent. Conversely, in dynamics, (c) is prominent, but (a) and (b) are not. The only fields that come to my mind that naturally exhibit all three of (a), (b), (c) (without also automatically exhibiting much richer algebraic structure, such as ring homomorphism structure) are complex dynamics, universal algebra, and certain types of cryptography, but I don't have enough experience in these fields to actually provide some interesting examples.

$\endgroup$
3
  • $\begingroup$ Very good point in the last paragraph. Together with the other answers (especially the one about information theory) my curiosity has pretty much been satisfied. $\endgroup$ Jan 28, 2011 at 0:01
  • 1
    $\begingroup$ 1+ Very illuminating $\endgroup$ Jan 28, 2011 at 9:21
  • $\begingroup$ See also math.la.asu.edu/~fpsac01/PROGRAM/bousquet.pdf . $\endgroup$
    – Max Muller
    Mar 10, 2011 at 17:11
18
$\begingroup$

I don't know if this actually counts (since I don't know if this functional equation is actually useful...), but in the paper

R.M. Dicker, A set of independent axioms for a field and a condition for a group to be the multiplicative group of a field, Proc. London Math. Soc., 18, 1968, p. 114-124

you can find the following theorem:

Let $A$ be an abelian group (written multiplicatively). Adjoin a new element $0$ to get the set $F$. Assume that there is a function $f : F \to F$ such that for all $x,y \in F$ with $y \neq 0$:

1) $f(0) = 1$

2) $f(f(x))=x$

3) $f(f(x) f(y)) = y f(x f(y^{-1}))$

Then $F$ can be made into a field such that $A = F^*$ and $f(x) = 1 - x$.

Here is another example from algebra which can be found in the article

Zoran Sunik, An Ideal Functional Equation with a Ring, Mathematics Magazine 77 (2004) 4, 310--313.

If $R$ is an integral domain, then the maps $f : R \to R$ solving the functional equation

$f(xz - y) f(x) f(y) + 3 f(0) = 1 + 2 f(0)^2 + f(x) f(y)$

are exactly the characteristic functions of ideals of $R$.

Also functional equations describing subrings and prime ideals are mentioned there.

$\endgroup$
1
  • $\begingroup$ These are nice examples. I have no idea if the second one is at all useful, but I have seen Connes use the first one in a paper on F_1 (I think). $\endgroup$ Jan 27, 2011 at 14:58
17
$\begingroup$

It is used a lot in information theory: See this.

$\endgroup$
1
  • $\begingroup$ +1. In fact, a couple of days ago I (re)borrowed from the library the book On Measures of Information and their Characterizations by Aczél and Daróczy, mentioned on the page Ross links to. It devotes many of its pages to... well, characterizing measures of information. For example, it discusses various known characterizations of Shannon entropy, giving theorems of the form "Shannon entropy is the unique function satisfying the following functional equations". $\endgroup$ Jan 27, 2011 at 9:00
17
$\begingroup$

Feigenbaum universal transition of a dynamical system (like the logistic map) to chaotic behaviour through period-doubling cascade involves the functional equation $$g(x)=-\frac1\lambda g(g(\lambda x))$$ with the boundary conditions $$g(0)=1,\qquad g'(0)=0,\qquad g''(0)<0.$$ The parameter $\lambda$ for which a solution exists near $x=0$ is the inverse of the Feigenbaum constant.

$\endgroup$
14
$\begingroup$

I think that the theorem of Ritt referred to in Borger's answer is the following: Let $f(x)$ and $g(x)$ be in $\textbf{C}(x)$, and suppose that they satisfy the functional equation $$f(g(x))=g(f(x)).$$ Then after conjugation by a linear fractional transformation, one of the following is true. (1) $f(x)=ax^n$ and $g(x)=bx^m$. (2) $f$ and $g$ are Cheybshev polynomials. (3) $f$ and $g$ are associated to endomorphisms of an elliptic curve (often called Lattes maps). (4) $f$ and $g$ have a common iterate, i.e., $f^m=g^n$ for some $m,n\ge1$.

The short way to say this is that the solutions to $f(g(x))=g(f(x))$ in rational functions are either associated to an algebraic group ($G_m$ for (1) and (2), an elliptic curve for (3)), or $f$ and $g$ have a common iterate.

$\endgroup$
2
  • $\begingroup$ There is a nice (and maybe more "readable/modern") proof of Ritt's theorem by Eremenko math.purdue.edu/~eremenko/dvi/feq-e.pdf. $\endgroup$
    – user5831
    Jan 27, 2011 at 17:02
  • $\begingroup$ Dear Joe -- That's actually not the theorem of Ritt's I had in mind, although it is one close to my heart. I've added the theorem I was thinking of to my response. $\endgroup$
    – JBorger
    Jan 28, 2011 at 0:34
12
$\begingroup$

I think it's mainly a problem of most Olympiad-style problems, rather than of functional equations -you may write down bizarre and unreal equations of any type, algebraic, ODE, PDE, integral, etc. Possibly, a reason of the "success" of functional equations in Olympiads is that they are somehow more elementary -no need of derivatives or even calculus, and are therefore more a suitable topic for these competitions. Yet important functional equations appear naturally everywhere; conjugation problems, to start with, in Algebra or in Dynamical Systems.

$\endgroup$
10
$\begingroup$

In enumerative combinatorics, you often end up with a functional equation for the generating function of the thing you're trying to count. These can involve compositions of the function with itself (and differentiation, exponential functions, ...) Often these don't have closed-form solutions, and you use them to get recurrences or asymptotics. Try searching for generating functions for labelled and unlabelled trees for some simple examples.

$\endgroup$
3
  • $\begingroup$ Good point, though the question seems to be mostly about closed-form solution. I do have to ask: do you have a simple example of obtaining recurrences this way? I'm not a specialist, and the only examples I can think of off the top of my head go the other way around: finding a functional equation from known recurrences. $\endgroup$ Jan 27, 2011 at 15:25
  • $\begingroup$ @Thierry: it is often more natural to write down a functional equation than a recurrence. For example, one definition of the Catalan numbers immediately gives C(x) = 1 + x C(x)^2, from which not only the standard recurrence but the standard closed form can be easily derived. There are more sophisticated examples (e.g. involving Lagrange inversion). $\endgroup$ Jan 27, 2011 at 15:55
  • 1
    $\begingroup$ Another nice example is the generating function for trees $A(x) = xE(A(x))$ where $E$ is the species of sets. $\endgroup$ Jan 28, 2011 at 20:17
5
$\begingroup$

There is a whole theory of functional equations (or functional identities) in algebras. It was used for instance to obtain solutions to some of Herstein's problems on Lie homomorphisms. An overview of the theory is given in the book

Bresar, Chebotar, Martindale, Functional identities

The area has its own entry in the 2010 MSC (16R60).

$\endgroup$
4
$\begingroup$

On page 47 of this pdf (page label 7-4) on complex dynamics, http://zakuski.math.utsa.edu/~jagy/Milnor_1991.pdf Milnor refers to the solution of $$ \alpha(f(z)) = 1 + \alpha(z) $$ in Theorem 7.7. In later editions that were published as actual books, he refers to $\alpha$ as a Fatou coordinate.

$\endgroup$
4
$\begingroup$

It seems there's a book on this subject.

$\endgroup$
3
$\begingroup$

Many problems in optimization (such as finding exact constants or maximizers to inequalities for linear operators) are equivalent to finding all solutions to associated Euler-Lagrange equations. Of course, these functional equations will involve the operator we started with, so they aren't elementary enough to be a satisfactory answer. However, sometimes these problems are solved by showing that the solutions (or related functions) must satisfy more elementary looking functional equations. As an example, here are some elementary looking functional equations: Find all complex-valued measurable functions that satisfy (almost everywhere) the equations:

1) $f(x)f(y) = F(|x|^2 +|y|^2, x+y)$ for $x,y \in R^2$,

2) $g(x)g(y) = G(|x|+|y|, x+y)$ for $x,y \in R^3$,

3) $h(x)h(y) = H(x^2 +y^2+z^2, x+y+z)$ for $x,y,z \in R$.

These and similar problems arise in the work of D. Foschi on maximizers to Strichartz inequalities in low dimensions.

$\endgroup$
3
$\begingroup$

I'm not sure if this is the kind of thing you want...

Let $\wp$ denote the Weierstrass $\wp$-function with respect to a lattice. Then for any integer $n$, there is a rational function $f(x)\in\mathbf{C}(x)$ (depending on the lattice) such that for all $z\in\mathbf{C}$, we have $\wp(nz)=f(\wp(z))$. This is just a disguised version of the fact that for a point $P$ on an elliptic curve in Weierstrass form, the $x$-coordinate of $nP$ depends only on the $x$-coordinate of $P$. In the "complex multiplication" case, where the ring of endomorphisms of the lattice is bigger than $\mathbf{Z}$ (in which case it's a rank two subring of $\mathbf{C}$), then such $f$'s exist for any endomorphism $n$.

I think Ritt classified the entire functions that admit algebraic functional equations.

[Added: Although it's now clear that this is not the direction the OP wanted to go in, I thought I might add a bit more detail for the record.

The paper of Ritt's I was thinking of is "Periodic functions with a multiplication theorem", Trans. Amer. Math. Soc. 23 (1922), no. 1, 16–25. He restricts himself to periodic functions $g$, but apparently he does allow them to be meromorphic. What he proves is that if a periodic meromorphic function $g$ has a functional equation of the form $g(nz)=f(g(z))$ for some $n\in\mathbf{C}$ and rational function $f$, then '$|n|\geq 1'$. If $|n|>1$, then $g$ is one of the following: (i) a linear function of a function of the form $\cos(az+b)$, (ii) a linear function of a function of the form $\exp(az)$, (iii) a function of the form $\wp(z+a)$, $\wp'(z+a)$, $\wp''(z+a)$, or $\wp'''(z+a)$. If $|n|=1$, then $g$ must be one of a short list of rational expressions in exponential functions and derivatives of $\wp$-functions.

(NB I haven't thought about the argument. I'm just copying from his paper. He also gives more detail about which possibilities occur when.)

Interestingly, he also mentions a result of Poincare that for any rational $f$ satisfying $f(0)=0$ and $|f(0)|>1$, there is a meromorphic function $g$ with functional equation $g(f'(0)z)=f(g(z))$.

And last, from what I remember, the theory of Drinfeld modules gives examples of analytic functions (such as the Carlitz exponential) over local fields of nonzero characteristic with similar functional equations. It would be interesting to prove a Ritt-like converse result in that case.]

$\endgroup$
2
  • 1
    $\begingroup$ This is a nice example, but it's another description of something highly structured: an algebraic group. Maybe I am more annoyed by the lack of structure in these questions than I am by the fact that they are functional equations... $\endgroup$ Jan 27, 2011 at 9:26
  • $\begingroup$ I've just been poking around and found that Ritt has other papers with similar themes, such as "Meromorphic functions with addition or multiplication theorems", Trans. Amer. Math. Soc. 29 (1927), no. 2, 341–360. $\endgroup$
    – JBorger
    Jan 28, 2011 at 0:45
2
$\begingroup$

A clone (in universal algebra) is a (graded by arity) set of functions on a base set A, which is closed under composition and contains n-ary projection functions p_i(abar) = a_i . Determining the structure of this clone is like finding out all the functional equations that can be satisfied on A using members of the clone.

If one can determine some such relations as whether one function distributes over another, this sometimes leads to normal forms. One can then build term-rewriting systems to simplify expressions or show some terms are equal to others (unification). In practice, many problems that we want to solve (logic minimization, satisfaction) turn out to be time- or space-intractable, if not undecidable.

I submit that clone theory is the study of a suitable generalization of your question. You might look at some recent papers to see if the field is of further interest to you.

Gerhard "Ask Me About System Design" Paseman, 2011.01.26

$\endgroup$
2
$\begingroup$

Since the question is about "really contrived functional equations" you should define what do you count as "really contrived". There are some important classes of functional equations.

  • Difference equations. They are discrete difference analogs of differential equations

  • Iterative equations. They usually can be reduced to difference equations

  • Delay differential equations. The combinations of difference and differential equations.

These classes are applied in many spheres. That's why they deserve to be researched. If you are speaking about equations that are outside of these classes, then indeed they are not frequently used in applied mathematics, but still may be interesting for research. Mathematicians research what they perceive as interesting, some research things that even in theory cannot be used in applied fields.

I also want to add some considerations about usefullness of solving completely random contrived equations. Such equations may lead to interesting insights into special functions and uncover interesting connections between them. Of course the mathematicians usually want to find general method which may be applicable not only to a particular equation but to a large class.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.