Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?"

share|improve this question
4  
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? –  Yemon Choi Jan 27 '11 at 1:19
2  
maybe try searching MathSciNet for all recent papers with primary MSC 39BXX? –  Willie Wong Jan 27 '11 at 1:33
2  
@Yemon: changed to "research." Does that sound better? –  Qiaochu Yuan Jan 27 '11 at 1:58
4  
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)... –  Terry Tao Jan 27 '11 at 10:35
2  
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 ... –  darij grinberg Jan 27 '11 at 10:48
show 9 more comments

14 Answers

up vote 27 down vote accepted

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.

share|improve this answer
    
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. –  Qiaochu Yuan Jan 28 '11 at 0:01
    
1+ Very illuminating –  Martin Brandenburg Jan 28 '11 at 9:21
    
See also math.la.asu.edu/~fpsac01/PROGRAM/bousquet.pdf . –  Max Muller Mar 10 '11 at 17:11
add comment

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

share|improve this answer
    
+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". –  Tom Leinster Jan 27 '11 at 9:00
add comment

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.

share|improve this answer
    
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). –  Qiaochu Yuan Jan 27 '11 at 14:58
add comment

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.

share|improve this answer
    
There is a nice (and maybe more "readable/modern") proof of Ritt's theorem by Eremenko math.purdue.edu/~eremenko/dvi/feq-e.pdf. –  user5831 Jan 27 '11 at 17:02
    
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. –  JBorger Jan 28 '11 at 0:34
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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. –  Thierry Zell Jan 27 '11 at 15:25
    
@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). –  Qiaochu Yuan Jan 27 '11 at 15:55
1  
Another nice example is the generating function for trees $A(x) = xE(A(x))$ where $E$ is the species of sets. –  Martin Rubey Jan 28 '11 at 20:17
add comment

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).

share|improve this answer
add comment

It seems there's a book on this subject.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.]

share|improve this answer
1  
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... –  Qiaochu Yuan Jan 27 '11 at 9:26
    
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. –  JBorger Jan 28 '11 at 0:45
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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