Suppose satisfies . What can we say about ?
which can happen if either or . Note that the function which is identically zero satisfies the functional equation. If is not this function, i.e., if for at least one value of , then plugging that value of (say ) into the equation gives . Also, for any , the equation forces as well. Further, so for all .
Next, putting gives , and by induction . Putting in place of in this gives which means (note we’re using here). And again, . So , which completely defines the function at rational points.
[As , it can be written as for some constant , which gives for rational .]
To extend this function to irrational numbers, we need some further assumptions on , such as continuity. It turns out that being continuous at any point is enough (and implies the function is everywhere): note that . Even being Lebesgue-integrable/measurable will do.
Else, there are discontinuous functions satisfying the functional equation. (Basically, we can define the value of the function separately on each “independent” part. That is, define the equivalence class where and are related if for rationals and , pick a representative for each class using the axiom of choice (this is something like picking a basis for , which corresponds to the equivalence class defined by the relation ), define the value of the function independently for each representative, and this fixes the value of on . See this article for more details.)
To step back a bit: what the functional equation says is that is a homorphism from , the additive group of real numbers, to , the multiplicative monoid of real numbers. If is not the trivial identically-zero function, then (as we saw above) is in fact a homomorphism from , the additive group of real numbers, to , the multiplicative group of positive real numbers. What we proved is that the exponential functions are precisely all such functions that are nice (nice here meaning either measurable or continuous at least one point). (Note that this set includes the trivial homomorphism corresponding to : the function identically everywhere. If is not this trivial map, then it is in fact an isomorphism.)
Edit [2013-10-11]: See also Overview of basic facts about Cauchy functional equation.
(Just some basic high-school physics stuff; to assure myself I can still do some elementary things. :P Essentially, showing that if a particle moves with acceleration perpendicular to velocity, or velocity perpendicular to position, then it traces out a circle. Stop reading here if this is obvious.)
Suppose a point moves in the plane such that its acceleration is always perpendicular to its velocity, and of the same magnitude. What is its path like?
To set up notation: let’s say the point’s position at time is , its velocity is , and its acceleration is .
The result of rotating a point by 90° is . (E.g. see figure below)
So the fact that acceleration is at right angles to velocity means that , or, to write everything in terms of the velocity,
where we can get rid of by substituting the second equation (in the form ) into the first:
or in other words
By some theory about ordinary differential equations, which I don’t know (please help!) (but see the very related example you saw in high school, of simple harmonic motion), the solutions to this equation are and and any linear combination of those: the solution in general is
where and is the angle such that and . And the fact that gives . So . Note that is indeed perpendicular to as we wanted.
The actual trajectory can be got by integrating
to get and . This trajectory is a point moving on a circle centered at point and of radius , with speed or unit angular speed. Note that velocity is also perpendicular to the point’s position wrt the centre of the circle, as velocity is tangential to the circle, as it should be.
With a suitable change of coordinates (translate the origin to , then rotate the axes by , then scale everything so that ), this is the familiar paremetrization of the circle.
Note: Just as we derived from assuming that the acceleration is perpendicular to velocity, we can, by assuming that velocity is perpendicular to position, identically derive , i.e. that the point moves on a circle.
Turns out it’s very easy, and we can basically use the same input method (UIM) as in Linux.
- Get MacUIM from its website
- Install it.
- Go to System Preferences -> Language & Text -> Input Sources, and turn on MacUIM. Tick “Show Input menu in menu bar” too.
- I now have three input methods: US, EasyIAST (see earlier post), and MacUIM (Roman).
- Go to System Preferences -> MacUIM -> General, and in Input method, choose m17n-kn-itrans
- Go to System Preferences -> MacUIM -> Helper, tick “Use Helper-Applet”, and in the list at the right, tick m17n-kn-itrans.
- [Just for me] I have some changes to kn-itrans.mim, to make it closer to HK (and remove nonsense like “RRi” or whatnot just to type ಋ): download this file kn-itrans.mim, and remove the pdf extension. It goes into /Library/M17NLib/share/m17n/kn-itrans.mim
These used to be ubiquitous a while ago (IIRC, I used to carry one of these daily to school as my lunch basket at some point; we still have one such basket at home), but photos seem hard to find on the internet (or I’m just missing the right keywords). So, photos:
There are many ways to derive the power series of and using the machinery of Taylor series etc., but below is another elementary way of demonstrating that the well-known power series expansions are the right ones. The argument below is from Tristan Needham’s Visual Complex Analysis, which I’m reproducing without looking at the book just to convince myself that I’ve internalized it correctly.
We will take the following two for granted (both can be proved with some effort):
- Both power series are convergent.
- The power series can be differentiated term-wise.
As suggested by (2) above, the first thing we observe is that and .
which means that is a constant and does not vary with . Putting shows that and , so for all .
Secondly, define the angle as a function of , by . (To be precise, this defines up to a multiple of , i.e. modulo .)
Differentiating the left-hand side of this definition gives
(where means )
while differentiating the right-hand side gives
The necessary equality of the two tells us that , which along with the initial condition that says , gives (or to be precise, ).
In other words, we have shown that the power series and satisfy and therefore and for some . The observation that (or our earlier observation that for all ) gives , thereby showing that and .
So much for and . Just as an aside, observe that if we take to be a symbol satisfying , then
the right hand side of which looks very much like the result of “substituting” in the known (real) power series
(which itself can be proved using the term-wise differentiation above and the defining property , say).
So this is one heuristic justification for us to define .
Or, if we define as the result of substituting in the real power series for , this proves that .
To type IAST (English letters with diacritics, for Sanskrit transliteration) on Mac OS X, perhaps the easiest way, rather than to use transliteration tools, is to get a keyboard layout that does it. Just to be clear, this is the alphabet we want:
a ā i ī u ū ṛ ṝ ḷ ḹ e ai o au ṃ ḥ k kh g gh ṅ c ch j j ñ ṭ ṭh ḍ ḍh ṇ t t d dh n p ph b bh m y r l v ś ṣ s h
In other words, the special characters needed are:
- Letters with macron above: ā ī ū ṝ ḹ plus it may be occasionally useful to have ē and ō as well
- Letters with dot below: ṭ ḍ ṇ ṣ (the retroflex consonants), also the vowels ṛ ṝ ḷ ḹ, plus ṃ and ḥ (anusvāra)
- Letters with other marks above: ṅ ñ ś
There is a keyboard layout that does this: It’s called “EasyUnicode”, created by Toshiya Unebe (Nagoya University), and is documented at http://ebmp.org/p_easyunicode.php (“EasyUnicode version 5″ it says) (PDF version), and you can download it from http://www.ebmp.org/p_dwnlds.php (EBMP) (=Early Buddhist Manuscripts Project, University of Washington) or also http://www.palitext.com/subpages/PC_Unicode.htm “Pali Fonts for PC and Unicode”. (Page in Japanese.)
This keyboard layout is just like the usual (US English) layout ordinarily, but when you hold down the Alt (Option) key and press a, you get ā, similarly Option+s gives ś, Option+n gives ñ and Option+g gives ṅ, etc. The full mapping is available along with other documentation in the download above.
This is very convenient. One issue with the layout is that also overrides a lot of keys for no apparent reason (Ctrl-A / Ctrl-E etc. stopped working for me), so I got Ukelele from SIL, and wrote my own keyboard layout. I’ve called it EasyIAST, and it is available here for now. I plan to add a README etc. and distribute it in some proper way later; for now you can use the instructions from EasyUnicode above. If you find it useful and/or make any improvements, please let me know as well.
If some time is available, it would be good to make a Devanagari keyboard layout along the same lines.
Sometime this week, I reread the first Harry Potter book (after at least 10 years… wow, has it been that long?), just for contrast after reading Rowling’s adult novel The Casual Vacancy (on which more later). Anyway, in the penultimate chapter there is a puzzle:
He pulled open the next door, both of them hardly daring to look at what came next — but there was nothing very frightening in here, just a table with seven differently shaped bottles standing on it in a line.
“Snape’s,” said Harry. “What do we have to do?”
They stepped over the threshold, and immediately a fire sprang up behind them in the doorway. It wasn’t ordinary fire either; it was purple. At the same instant, black flames shot up in the doorway leading onward. They were trapped.
“Look!” Hermione seized a roll of paper lying next to the bottles. Harry looked over her shoulder to read it:
Danger lies before you, while safety lies behind,
Two of us will help you, whichever you would find,
One among us seven will let you move ahead,
Another will transport the drinker back instead,
Two among our number hold only nettle wine,
Three of us are killers, waiting hidden in line.
Choose, unless you wish to stay here forevermore,
To help you in your choice, we give you these clues four:
First, however slyly the poison tries to hide
You will always find some on nettle wine’s left side;
Second, different are those who stand at either end,
But if you would move onward, neither is your friend;
Third, as you see clearly, all are different size,
Neither dwarf nor giant holds death in their insides;
Fourth, the second left and the second on the right
Are twins once you taste them, though different at first sight.
I became curious about whether this is just a ditty Rowling made up, or the puzzle actually makes sense and is consistent. It turns out she has constructed it well. Let’s take a look. This investigation can be carried out by hand, but we’ll be lazy and use a computer, specifically Python. The code examples below are all to be typed in an interactive Python shell, the one that you get by typing “python” in a terminal.
So what we have are seven bottles, of which one will take you forward (F), one will let you go back (B), two are just nettle wine (N), and three are poison (P).
>>> bottles = ['F', 'B', 'N', 'N', 'P', 'P', 'P']
The actual ordering of these 7 bottles is some ordering (permutation) of them. As 7 is a very small number, we can afford to be inefficient and resort to brute-force enumeration.
>>> import itertools >>> perms = [''.join(s) for s in set(itertools.permutations(bottles))] >>> len(perms) 420
set is needed to remove duplicates, because otherwise
itertools.permutations will print 7! “permutations”. So already the number of all possible orderings is rather small (it is ). We can look at a sample to check whether things look fine.
>>> perms[:10] ['PNFNPBP', 'NPPBNFP', 'FNNPBPP', 'PPPFNBN', 'NPPNBFP', 'PFNNBPP', 'NPBPPFN', 'NBNPPFP', 'NPPFBNP', 'BNPFNPP']
Now let us try to solve the puzzle. We can start with the first clue, which says that wherever a nettle-wine bottle occurs, on its left is always a poison bottle (and in particular therefore, a nettle-wine bottle cannot be in the leftmost position). So we must restrict the orderings to just those that satisfy this condition.
>>> def clue1(s): return all(i > 0 and s[i-1] == 'P' for i in range(len(s)) if s[i]=='N') ... >>> len([s for s in perms if clue1(s)]) 60
(In the code, the 7 positions are 0 to 6, as array indices in code generally start at 0.)
Then the second clue says that the bottles at the end are different, and neither contains the potion that lets you go forward.
>>> def clue2(s): return s != s and s != 'F' and s != 'F' ... >>> len([s for s in perms if clue1(s) and clue2(s)]) 30
The third clue says that the smallest and largest bottles don’t contain poison, and this would be of help to Harry and Hermione who can see the sizes of the bottles. But as we readers are not told the sizes of the bottles, this doesn’t seem of any help to us; let us return to this later.
The fourth clue says that the second-left and second-right bottles have the same contents.
>>> def clue4(s): return s == s ... >>> len([s for s in perms if clue1(s) and clue2(s) and clue4(s)]) 8
There are now just 8 possibilities, finally small enough to print them all.
>>> [s for s in perms if clue1(s) and clue2(s) and clue4(s)] ['PPNBFPN', 'BPNPFPN', 'BPFPNPN', 'BPPNFPN', 'PNPFPNB', 'BPNFPPN', 'PPNFBPN', 'PNFPPNB']
Alas, without knowing which the “dwarf” and “giant” bottles are, we cannot use the third clue, and this seems as far as we can go. We seem to have exhausted all the information available…
Almost. It is reasonable to assume that the puzzle is meant to have a solution. So even without knowing where exactly the “dwarf” and “giant” bottles are, we can say that they are in some pair of locations that ensure a unique solution.
>>> def clue3(d, g, s): return s[d]!='P' and s[g]!='P' ... >>> for d in range(7): ... for g in range(7): ... if d == g: continue ... poss = [s for s in perms if clue1(s) and clue2(s) and clue4(s) and clue3(d,g,s)] ... if len(poss) == 1: ... print d, g, poss ... 1 2 PNFPPNB 1 3 PNPFPNB 2 1 PNFPPNB 2 5 PNFPPNB 3 1 PNPFPNB 3 5 PNPFPNB 5 2 PNFPPNB 5 3 PNPFPNB
Aha! If you look at the possible orderings closely, you will see that we are down to just two possibilities for the ordering of the bottles.
Actually there is some scope for quibbling in what we did above: perhaps we cannot say that there is a unique solution determining the entire configuration; perhaps all we can say is that the puzzle should let us uniquely determine the positions of just the two useful bottles. Fortunately, that gives exactly the same set of possibilities, so this distinction happens to be inconsequential.
>>> for d in range(7): ... for g in range(7): ... if d == g: continue ... poss = [(s.index('F'),s.index('B')) for s in perms if clue1(s) and clue2(s) and clue4(s) and clue3(d,g,s)] ... if len(set(poss)) == 1: ... print d, g, [s for s in perms if clue1(s) and clue2(s) and clue4(s) and clue3(d,g,s)] ... 1 2 PNFPPNB 1 3 PNPFPNB 2 1 PNFPPNB 2 5 PNFPPNB 3 1 PNPFPNB 3 5 PNPFPNB 5 2 PNFPPNB 5 3 PNPFPNB
Good. Note that there are only two configurations above. So with only the clues in the poem, and the assumption that the puzzle can be solved, we can narrow down the possibilities to two configurations, and be sure of the contents of all the bottles except the third and fourth. We know that the potion that lets us go forward is in either the third or the fourth bottle.
In particular we see that the last bottle lets us go back, and indeed this is confirmed by the story later:
“Which one will get you back through the purple flames?”
Hermione pointed at a rounded bottle at the right end of the line.
She took a long drink from the round bottle at the end, and shuddered.
But we don’t know which of the two it is, as we can’t reconstruct all the relevant details of the configuration. Perhaps we can reconstruct something with the remaining piece of information from the story?
“Got it,” she said. “The smallest bottle will get us through the black fire — toward the Stone.”
Harry looked at the tiny bottle.
Harry took a deep breath and picked up the smallest bottle.
So we know that the bottle that lets one move forward is in fact in the smallest one, the “dwarf”.
>>> for d in range(7): ... for g in range(7): ... poss = [s for s in perms if clue1(s) and clue2(s) and clue4(s) and clue3(d,g,s)] ... if len(poss) == 1 and poss[d] == 'F': ... print d, g, poss ... 2 1 PNFPPNB 2 5 PNFPPNB 3 1 PNPFPNB 3 5 PNPFPNB
This narrows the possible positions of the smallest and largest bottles (note that it says the largest bottle is one that contains nettle wine), but still leaves the same two possibilities for the complete configuration. So we can stop here.
What we can conclude is the following: apart from the clues mentioned in the poem, the “dwarf” (the smallest bottle) was in either position 2 (third from the left) or 3 (fourth from the left). The biggest bottle was in either position 1 (second from the left) or 5 (sixth from the left). With this information about the location of the smallest bottle (and without necessarily assuming the puzzle has a unique solution!), Hermione could determine the contents of all the bottles. In particular she could determine the location of the two useful bottles: namely that the bottle that lets you go back was the last one, and that the one that lets you go forward was the smallest bottle.
>>> for (d,g) in [(2,1), (2,5), (3,1), (3,5)]: ... poss = [s for s in perms if clue1(s) and clue2(s) and clue4(s) and clue3(d, g, s)] ... assert len(poss) == 1 ... s = poss ... assert s.index('B') == 6 ... assert s.index('F') == d ... print (d,g), s ... (2, 1) PNFPPNB (2, 5) PNFPPNB (3, 1) PNPFPNB (3, 5) PNPFPNB
It is not clear why she went to the effort to create a meaningful puzzle, then withheld details that would let the reader solve it fully. Perhaps some details were removed during editing. As far as making up stuff for the sake of a story goes, though, this is nothing; consider for instance the language created for Avatar which viewers have learned.
See also http://www.zhasea.com/logic/snape.html which does it by hand, and has a perfectly clear exposition (it doesn’t try the trick of guessing that solution is unique before reaching for the additional information from the story).