The Lumber Room

The functional equation f(x+y) = f(x)f(y)

Suppose $f: \mathbb{R} \to \mathbb{R}$ satisfies $f(x+y) = f(x) f(y)$ . What can we say about $f$ ?

Putting $y = 0$ gives

$\displaystyle f(x) = f(x+0) = f(x)f(0),$

which can happen if either $f(x) = 0$ or $f(0) = 1$ . Note that the function $f$ which is identically zero satisfies the functional equation. If $f$ is not this function, i.e., if $f(x) \neq 0$ for at least one value of $x$ , then plugging that value of $x$ (say $x^*$ ) into the equation gives $f(0) = 1$ . Also, for any $x$ , the equation $f(x^*) = f(x +x^* - x) = f(x)f(x^* - x)$ forces $f(x) \neq 0$ as well. Further, $f(x) = f(x/2 + x/2) = f(x/2)^2$ so $f(x) > 0$ for all $x$ .

Next, putting $y = x$ gives $f(2x) = f(x)^2$ , and by induction $f(nx) = f(x)^n$ . Putting $\frac{x}{n}$ in place of $x$ in this gives $f(n\frac{x}{n}) = f(\frac{x}{n})^n$ which means $f(\frac{x}{n}) = f(x)^{\frac1n}$ (note we’re using $f(x) > 0$ here). And again, $f(\frac{m}{n}x) = f(x)^{m/n}$ . So $f(\frac{m}{n}) = f(1)^{m/n}$ , which completely defines the function at rational points.

[As $f(1) > 0$ , it can be written as $f(1) = e^k$ for some constant $k$ , which gives $f(x) = e^{kx}$ for rational $x$ .]

To extend this function to irrational numbers, we need some further assumptions on $f$ , such as continuity. It turns out that being continuous at any point is enough (and implies the function is $f(x) = f(1)^x$ everywhere): note that $f(x + m/n) = f(x)f(m/n) = f(x)f(1)^{m/n}$ . 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 $x$ and $y$ are related if $y = r_1x + r_2$ for rationals $r_1$ and $r_2$ , pick a representative for each class using the axiom of choice (this is something like picking a basis for $\mathbb{R}/\mathbb{Q}$ , which corresponds to the equivalence class defined by the relation $y = r_1x$ ), define the value of the function independently for each representative, and this fixes the value of $f$ on $\mathbb{R}$ . See this article for more details.)

To step back a bit: what the functional equation says is that $f$ is a homorphism from $(\mathbb{R}, +)$ , the additive group of real numbers, to $(\mathbb{R}, \times)$ , the multiplicative monoid of real numbers. If $f$ is not the trivial identically-zero function, then (as we saw above) $f$ is in fact a homomorphism from $(\mathbb{R}, +)$ , the additive group of real numbers, to $(\mathbb{R_+^*}, \times)$ , the multiplicative group of positive real numbers. What we proved is that the exponential functions $e^{kx}$ 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 $k = 0$ : the function $f(x) = 1$ identically everywhere. If $f$ is not this trivial map, then it is in fact an isomorphism.)

Written by S

Mon, 2013-04-08 at 11:24:08 +05:30

Posted in mathematics

Trajectory of a point moving with acceleration perpendicular to velocity

with 7 comments

(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 $t$ is $(p_x(t), p_y(t))$ , its velocity is $(v_x(t), v_y(t)) = \left(\frac{d}{dt}p_x(t), \frac{d}{dt}p_y(t)\right)$ , and its acceleration is $(a_x(t), a_y(t)) = \left(\frac{d}{dt}v_x(t), \frac{d}{dt}v_y(t)\right)$ .

The result of rotating a point $(x,y)$ by 90° is $(-y, x)$ . (E.g. see figure below)

rotate90

So the fact that acceleration is at right angles to velocity means that $(a_x(t), a_y(t)) = (-v_y(t), v_x(t))$ , or, to write everything in terms of the velocity,

$\begin{aligned} \frac{d}{dt}v_x(t) &= -v_y(t) \\ \frac{d}{dt}v_y(t) &= v_x(t) \end{aligned}$

where we can get rid of $v_x(t)$ by substituting the second equation (in the form $v_x(t) = \frac{d}{dt}v_y(t)$ ) into the first:

$v_y(t) = -\frac{d}{dt}v_x(t) = -\frac{d}{dt}\left(\frac{d}{dt}v_y(t)\right)$

or in other words

$v_y(t) = -\frac{d^2}{dt^2}v_y(t).$

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 $\sin(t)$ and $\cos(t)$ and any linear combination of those: the solution in general is

$\begin{aligned} v_y(t) &= a \sin(t) + b \cos(t) \\ &= \sqrt{a^2 + b^2} \left(\frac{a}{\sqrt{a^2+b^2}}\sin(t) + \frac{b}{\sqrt{a^2+b^2}}\cos(t)\right) \\ &= R\sin (t + \alpha) \end{aligned}$

where $R = \sqrt{a^2 + b^2}$ and $\alpha$ is the angle such that $\cos(\alpha) = \frac{a}{\sqrt{a^2+b^2}}$ and $\sin(\alpha) = \frac{b}{\sqrt{a^2+b^2}}$ . And the fact that $v_x(t) = \frac{d}{dt}v_y(t)$ gives $v_x(t) = R\cos(t + \alpha)$ . So $(v_x(t), v_y(t)) = (R\cos(t + \alpha), R\sin(t + \alpha))$ . Note that $(a_x(t), a_y(t)) = \left(\frac{d}{dt}v_x(t), \frac{d}{dt}v_y(t)\right) = (-R\sin(t+\alpha), R\cos(t+\alpha))$ is indeed perpendicular to $(v_x(t), v_y(t))$ as we wanted.

The actual trajectory $(p_x(t), p_y(t))$ can be got by integrating

$\left(\frac{d}{dt}p_x(t), \frac{d}{dt}p_y(t)\right) = (v_x(t), v_y(t)) = (R\cos(t + \alpha), R\sin(t + \alpha))$

to get $p_x(t) = R\sin(t + \alpha) + c_1$ and $p_y(t) = -R\cos(t + \alpha) + c_2$ . This trajectory is a point moving on a circle centered at point $(c_1, c_2)$ and of radius $R$ , with speed $R$ 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 $(c_1, c_2)$ , then rotate the axes by $\frac{\pi}{2}+\alpha$ , then scale everything so that $R = 1$ ), this is the familiar paremetrization $(\cos(t), \sin(t))$ of the circle.

Note: Just as we derived $(v_x(t), v_y(t)) = (R\cos(t + \alpha), R\sin(t + \alpha))$ from assuming that the acceleration is perpendicular to velocity, we can, by assuming that velocity is perpendicular to position, identically derive $(p_x(t), p_y(t)) = (R\cos(t + \alpha), R\sin(t + \alpha))$ , i.e. that the point moves on a circle.

Written by S

Sun, 2013-04-07 at 23:38:01 +05:30

Posted in mathematics

Typing Kannada on Mac OS X

Plastic wire baskets

The power series for sin and cos

A better keyboard layout for typing IAST on Mac OS X (based on EasyUnicode)

with 3 comments

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.

Written by S

Tue, 2013-01-22 at 11:28:55 +05:30

Posted in sanskrit

Tagged with IAST, input, software

The potions puzzle by Snape in Harry Potter and the Philosopher’s Stone

with one comment

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

The 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 $\frac{7!}{2!3!} = 420$ ). 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[0] != s[6] and s[0] != 'F' and s[6] != '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[1] == s[5]
...
>>> 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[0]
... 
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)][0]
... 
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[0][d] == 'F':
...       print d, g, poss[0]
... 
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.

Conclusion
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[0]
...   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.

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

Written by S

Mon, 2012-10-22 at 02:00:12 +05:30

Posted in entertainment, mathematics

Tagged with harry potter, programming, puzzle

S	M	T	W	T	F	S
« Apr
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

The Lumber Room

The functional equation f(x+y) = f(x)f(y)

Trajectory of a point moving with acceleration perpendicular to velocity

Typing Kannada on Mac OS X

Plastic wire baskets

The power series for sin and cos

A better keyboard layout for typing IAST on Mac OS X (based on EasyUnicode)

The potions puzzle by Snape in Harry Potter and the Philosopher’s Stone

Pages

Archives

Tags

Meta

Blog Stats

Follow “The Lumber Room”