23:02:00   Olimpiade Matematika,

I solved IMO problem 5 with the "density" style,  this is not that precise actual density from the topology course. High School students usually view 'dense' as "always getting somewhere in between". Note that (until this post got published) this proof is quite different from the proofs given in Mathlinks.

IMO 2013 Problem 5
Find all function $f: \mathbb{Q}_+\rightarrow \mathbb{R}$ which satisfies:
a) $f(x+y) \geq f(x)+f(y)$ for all $x, y \in \mathbb{Q}_+$.
b) $f(x)f(y) \geq f(xy)$ for all $x, y \in \mathbb{Q}_+$.
c) There exists $a\in \mathbb{Q}_+$ and $a> 1$ such that $f(a)=a$.

Solution: 

We first prove the following lemma:

Lemma: The set $A:=\left\{\frac{a^k}{n} \lvert k, n \in \mathbb{N}\right\}$ is "dense" in $\mathbb{Q}_+$. That is for any $x, y \in \mathbb{Q}_+$ there exists $\theta \in A$ such that $x < \theta < y$.

Proof: 
Given $x, y \in \mathbb{Q}_+$ with $y> x$, since $a> 1$ we can choose $k$ large enough so that $\frac{a^k}{x}-\frac{a^k}{y}=a^k \left(\frac{y-x}{xy}\right)> 1$. Therefore there exists an integer $N$ in the interval $\left(\frac{a^k}{y},\frac{a^k}{x}\right)$. Thus

\[\frac{a^k}{y} < N < \frac{a^k}{x}\]

This means $x < \frac{a^k}{N} < y$. $\blacksquare$.

From condition 3, we have $f(a)=a >  0$, thus $f(1)a=f(1)f\left(a\right) \geq f\left(a\right) = a$. Therefore $f(1) \geq 1$.

Next we will prove that $f(n)\geq n$ for all $n \in \mathbb{N}$.
Obviously, we have $f(x_1+x_2+\cdots+x_n)\geq f(x_1)+f(x_2)+\cdots+f(x_n)$. 
Thus $f(n)\geq f(1)n \geq n$.

Next we will prove that $f(x) > 0$ for all $x \in \mathbb{Q}_+$. Suppose that there exists a positive rational number $t$ such that $f(t) \leq 0 $ choose a positive integer $s$ such that $st$ is an integer. Hence since $f(s)\geq s > 0$ we have $st\leq f(st) \leq f(s) f(t) \leq 0$, a contradiction.

Then we prove that $f$ is monotonely increasing, for any positive rational numbers $y > x$, then $y=x+ t$ for some positive rational number $t$. Thus $f(y)= f(x+t)\geq f(x)+f(t) > f(x)$.

We have $f(a^k)\leq f(a)^k = a^k$ thus for any integers $m$ and $k$ we have $m f\left(\frac{a^k}{m}\right) \leq f(a^k) \leq a^k$ which implies
\[f\left(\frac{a^k}{m}\right)\leq \frac{a^k}{m} \qquad \text{for any integers $k,  m$}\]

We will prove that $f(r)\leq r$ for all $r \in \mathbb{Q}_+$. Suppose that there exists a  positive rational number $r$ such that $f(r) > r$, fix a natural number $k$ , then $v:=\frac{a^{k+1}}{f(r)-r}$ is a defined positive number. Thus we can take an integer $m$ greater than $v$.

But, by our lemma, between $r+\frac{a^k}{m}$ and $r+\frac{a^{k+1}}{m}$ there exists a rational number of the form $\frac{a^l}{u}$, hence by the monotonity we have

\[f(r) < f\left(r+\frac{a^k}{m}\right) < f\left(\frac{a^l}{u}\right) \leq \frac{a^l}{u} < r+\frac{a^{k+1}}{m} \]

But then $m < \frac{a^{k+1}}{f(r)-r} =v$ a contradiction. Thus for all positive rational numbers $r$ we have $f(r)\leq  r$ , in particular $f(n)\leq n$ for all natural numbers, since we also have $f(n)\geq n$ we conclude that $f(n)=n$ for all natural numbers $n$.

For any rational numbers $\frac{b}{c}$ where $b$ and $c$ are positive integers we have $f\left(\frac{b}{c}\right) \geq \frac{f(b)}{f(c)}=\frac{b}{c}$, therefore $f(r)\geq r$ for all $r\in \mathbb{Q}_+$, since $f(r)\leq r$ as well, we conclude that $f(r)=r$. It is easy to check that this function satisfies the given conditions. 

Continue Reading

Part I of Explicit Construction of the Elliptic Curve (CIMPA School)

Part I of Explicit Construction of the Elliptic Curve (CIMPA School)

08:53:00   Algebraic,

The following is based on Stevenhaagen's talk on 2013 CIMPA School in Manila. This write is a little bit mess, as actually a lot of things need to be proved. I'm just trying to connect the preliminaries introduced so far.

Recall from my previous post  a Weierstrass Elliptic Function is given by

\[\wp(z)=\frac{1}{z^2} + \sum_{\omega \in A/\{0\}} \left(\frac{1}{(z-\omega)^2} - \frac{1}{\omega^2}\right)\]

By the doubly periodicity, let's take the restriction of the domain inside a fundamental lattice $L$ .  This function also satisfies the differential equation

\[{\wp^{\prime}(z)}^2 = 4 \wp(z)^3-g_2(L)\wp(z)-g_3(L)\]

where $g_1(L)$ and $g_2(L)$ are modular forms given by $g_2(L)=60 \sum_{\omega \in L/\{0\}} \frac{1}{\omega^4}$ and $g_3(L)=140 \sum_{\omega \in L/\{0\}} \frac{1}{\omega^6}$.

Therefore we can define the parametrization of a torus $T:=\mathbb{C} \pmod L$ to a Projective Plane by the equation of  Elliptic curve
\[y^2=4x^3-g_2(L)x-g_3(L)\]
with dehomogenization \[y^2z=4x^3-g_2(L)xz^2-g_3(L)z^3\]

The map is given by $z \mapsto (\wp(z),\wp^{\prime}(z),1)$  and $0 \mapsto (0,1,0)$, this map is an injective function from $T$ to Elliptic Curve.

We also define the $j$-invariant of the Latice L by 

\[j(L)=1728\frac{g_2(L)^3}{g_2(L)^3-27g_3(L)^2}\]

this value is always defined whenever $L$ is indeed  a lattice ($g_2(L)^3-27g_3(L)^2 \neq 0$).

Now for a complex number $\tau$ in a Upper Half plane $\mathcal{H}$, define the lattice $L_{\tau}$ as the lattice generated by $1$ and $\tau$, we write $L_{\tau}=[1,\tau]$.  It can be shown that every lattice $L=[z_1,z_2]$ is isomorphic (or sometimes' called homothetic) to $L_{\tau}$  for some $\tau \in \mathcal{H}$ (this can be seen by setting $\tau=\frac{z_2}{z_1}$). Therefore we can view $j$ as the function $j : \mathcal{H} \rightarrow \mathbb{C}$ with

\[j(\tau)=j(L_{\tau}) = 1728\frac{g_2(L_{\tau})^3}{g_2(L_{\tau})^3-27g_3(L_{\tau})^2}\]

We call this function the $j$-function.  The key point is that this function is a modular form of weight 0, i.e modular function, i.e

\[j(A \cdot \tau) = j(\tau)\]

for $A \in SL_2(\mathbb{Z})$, and $A \cdot \tau$ denotes the Mobius action.

The condition that $\tau$ is on the Upper Half Plane is good for redefine the function $j$ on the smaller subset of $\mathcal{H}$ which is a  fundamental domain $\mathcal{D}$ given by

\[\mathcal{D}=\left\{\tau \in \mathcal{H} \, \lvert \, \Re(\tau) \in \left[-\frac{1}{2},\frac{1}{2}\right), \tau > 1 \right\} \cup \{\tau \in \mathcal{H} \, \lvert \, \Re(\tau) \geq 0 \mbox{ if } |\tau|=1 \}\] 

this fundamental domain will correspond each $\tau \in \mathcal{D}$ into $\tau=\frac{-b+\sqrt{b^2-4ac}}{2a}$, where $a,b$ and $c$ are coprime integer satisfying 

\[|b|\leq a \leq c \text{ and } b\geq 0  \text{ whenever } |b|=a \text{ or } a=c\]

We call the function $f(x,y)=ax^2+bxy+cy^2$ a reduced quadratic form whenever $(a,b,c)$ satisfying the above conditions. Therefore $\tau \in \mathcal{D}$ whenever $\tau$ is the (half-plane) root of $f(x,1)$ for a reduced quadratic form $f(x,y)$.

Now given a negative integer $D$,  we collect all the reduced quadratic form $f(x,y)=ax^2+bxy+cy^2$ such that $D=b^2-4ac$,  it turns out that this collection say $Cl(D)$ is a class group. More interesting is that we can adjoint $j(\tau)=j\left(\frac{-b+\sqrt{b^2-4ac}}{2a}\right)$ to $K=\mathbb{Q}(\sqrt{D})$ where $D$ is a fundamental discriminant, such that $j(\tau)$ is algebraic in this extension!! We called this extension a Hilbert Class Field, and the minimum polynomial $H_K$ is called Hilbert Class Polynomial and it is in $\mathbb{Z}[X]$. 

Continue Reading

Pedantic On Mathematical Software (Middle School Algebra)

Pedantic On Mathematical Software (Middle School Algebra)

17:37:00  

This time Maple get it wrong while Wolfram get it flawlessly. Consider the following middle-school level problem:

Solve the following equation on $x$

\[\sqrt{x+3-4\sqrt{x-1}}+\sqrt{x+8-6\sqrt{x-1}}=1\]

Solution:

The equation is equivalent to $\sqrt{\left(\sqrt{x-1}-2\right)^2}+\sqrt{\left(\sqrt{x-1}+3
\right)^2}=1$ so that we have

\[\left|\sqrt{x-1}-2\right|+\left|\sqrt{x-1}-3\right|=1\]

We divide into three cases:

i) When $\sqrt{x-1}< 2$ then we have $\sqrt{x-1}< 3$ so that  the above equation becomes
\[2-\sqrt{x-1}+3-\sqrt{x-1}=1\]
that is $\sqrt{x-1}=2$, contradicting $\sqrt{x-1}< 2$.

ii) When $\sqrt{x-1}> 3$ then we have $\sqrt{x-1}> 2$ so that the equation becomes
\[\sqrt{x-1}-2+\sqrt{x-1}-3=1\]
that is $\sqrt{x-1}=3$, contradicting $\sqrt{x-1}> 3$.

ii) When $2\leq \sqrt{x-1}\leq 3$ then we have
\[\sqrt{x-1}-2+3-\sqrt{x-1}=1\]
which is equivalent to $1=1$, and so all $x$ on this case are the solutions, those are $x\in [5,10]$.

However, if you input the command

\[solve(\sqrt{x+3-4\sqrt{x-1}}+\sqrt{x+8-6\sqrt{x-1}}-1,x)\]

into Maple 16, it gives you an output

\[x=x\]

Other math  software like Wolfram Mathematica gives us the correct answer $5\leq x \leq 10$.

Using the method of squaring you'll get $1=1$ as well.
Continue Reading

Pedantic on Mathematical Software [Trap Limit]

Pedantic on Mathematical Software [Trap Limit]

08:11:00  

Wolfram Alpha result for

\[\lim_{x\rightarrow 0}\frac{\sin \left(x\sin\left(\frac{1}{x}\right)\right)}{x\sin \left(\frac{1}{x}\right)}\]

is "No result found in terms of standard mathematical functions" while Maple clearly says  the limit is  "Undefined".  Notice that Wolfram Alpha will say "The Limit Does Not Exist" for $\lim_{x\rightarrow 0} \sin \left(\frac{1}{x}\right)$.

Indeed Maple is right, the limit does not exist. It is important to notice that the following solution is wrong

\[\lim_{x\rightarrow 0} x\sin \frac{1}{x}=0 \qquad \text{and} \qquad \lim_{x\rightarrow 0} \frac{\sin{x}}{x}=1\] Then \[\lim_{x\rightarrow 0}\frac{\sin \left(x\sin\left(\frac{1}{x}\right)\right)}{x\sin \left(\frac{1}{x}\right)}=\lim_{x\sin \frac{1}{x} \rightarrow 0} \frac{\sin \left(x\sin\left(\frac{1}{x}\right)\right)}{x\sin \left(\frac{1}{x}\right)}=\lim_{y\rightarrow 0} \frac{\sin y}{y}=1\]

First, we cannot use the composition law of limit here, the law says that:

[Substitution Rule] Suppose that as $x\rightarrow a$, $g(x)$ converges properly to $A$ and that \[\lim_{y\rightarrow A} f(y)=L.\]
Then
\[\lim_{x\rightarrow a} f(g(x))=L\]

Though, $\lim_{x\rightarrow 0} x \sin\frac{1}{x}=0$, the convergent is not proper, thus the above rule can't be applied.

To see why the limit does not exist, We look back at the definition of the limit, we say that such a limit exists if we can find a real number $L$, such that:

\[\forall \epsilon > 0 \exists \delta > 0 , \forall x, \, \, \,  0< |x-c| < \delta \Rightarrow \left|f(x)-L\right| < \epsilon \]

The problem is:  for every $L \in \mathbb{R}$,  given an $\epsilon > 0$,  no matter how small we choose a neighbourhood of $0$ (by choosing a sufficiently small $\delta$), the function $x\sin \frac{1}{x}$ can be equal to zero for infinitely many values of $x$ on that neighbourhood, thus the function
\[\frac{\sin \left(x\sin\left(\frac{1}{x}\right)\right)}{x\sin \left(\frac{1}{x}\right)}\]
is undefined (infinitely many times) on that neighbourhood.

In other words, it is impossible for us to choose a neighbourhood around $0$ such that the function
\[\frac{\sin \left(x\sin\left(\frac{1}{x}\right)\right)}{x\sin \left(\frac{1}{x}\right)}\]
is defined on all points on that neighbourhood, hence no such $\delta$ can be chosen on the definition of limit, thus the limit does not exist.

More formally, for any $\delta > 0$, by Archimedean Principle there exists a positive integer $N$ such that $N>\frac{1}{2\pi \delta}$, thus we have $x_k=\frac{1}{2k\pi} \in (0,\delta)$ for every $k\geq N$, and on these points we have $x_k \sin \frac{1}{x_k} = 0$.

Continue Reading

Soal Persamaan Fungsi

Soal Persamaan Fungsi

20:07:00   Olimpiade Matematika,

Sebenarnya post ini cuma mau nge-test LaTex di Dynamic View nya blogger. Tapi ya sekalian kasi soal-Soal Fungsi berikut saya anggap susah.

Source nya nggak disebutkan, ada yang saya tahu ada yang saya lupa  (itung-itung buat yang mau latihan bisa ngilangin temptation untuk nge-browse solusinya di Mathlinks :D )
 ------------------------------------------------------
1. Tentukan semua fungsi $f : \mathbb{R}^+ \rightarrow \mathbb{R}^+$ yang memenuhi
\[f(x)f(y)=f(y)f(xf(y))+\frac{1}{xy}\]

2. Tentukan semua fungsi $f: \mathbb{R} \rightarrow \mathbb{R}$ yang memenuhi : untuk setiap $x,y\in \mathbb{R}$
\[f(y+f(x))=f(x)f(y)+f(f(x))+f(y)-xy\]
untuk setiap $x,y \in \mathbb{R}$.

3. Tentukan semua fungsi $f: \mathbb{R}^+ \rightarrow \mathbb{R}^+$ yang memenuhi: untuk setiap $x,y\in \mathbb{R}^+$
\[f(x)f(y)=2f(x+yf(x))\]

4. Misalkan $f(x) \in \mathbb{Z}[x]$ dengan $\text{deg}(f(x))=4$, buktikan terdapat $M \in \mathbb{N}$ sedemikian sehingga \[f(n!) \equiv \pmod {2^n-1}\] untuk setiap $n>M$

5. Tentukan semua fungsi $f: \mathbb{N} \rightarrow \mathbb{N}$ yang memenuhi: untuk setiap $m,n \in \mathbb{N}$
\[f(m^2+f(n))=f(m)^2+n\]

6. Tentukan semua fungsi $f: \mathbb{R}\rightarrow \mathbb{R}$ yang memenuhi: untuk setiap $x,y\in \mathbb{R}$
\[f(xf(x+y))=f(yf(x))+x^2\]

7. Tentukan semua fungsi $f:\mathbb{R} \rightarrow \mathbb{R}$ yang memenuhi: untuk setiap $x,y\in \mathbb{R}$
\[f(x-f(y))=f(f(y))+xf(y)+f(x)-1\]

8. Tentukan semua  fungsi $f: \mathbb{N} \rightarrow \mathbb{N}$ yang memenuhi untuk setiap $m,n \in \mathbb{N}$
\[f(f(m)^2+2f(n)^2)=m^2+2n^2\]

9. Tentukan semua fungsi $f:\mathbb{R} \rightarrow \mathbb{R}$ yang memenuhi: untuk setiap $x\in \mathbb{R}$ berlaku
\[f(x^2)=f(x)^2 \qquad \text{dan} \qquad f(x+1)=f(x)+1\]

10.Misalkan $f:\mathbb{R} \rightarrow \mathbb{R}$ fungsi monoton tak turun yang memenuhi
\[f(x+f(y))=f(f(x))+f(y)\]
untuk setiap $x,y \in \mathbb{R}$

Continue Reading

Exercises

Exercises

04:31:00   Olimpiade Matematika,

Solution for problem 11 is taken from American Math Monthly. Yes, Forgot to type solution for No 1, but maybe I don't need to, It's an easy problem :)

Problems

Solutions

Continue Reading