수학 이론(39)
-
Beatty Sequence와 Rayleigh's theorem
시험기간인데 포스팅은 하고 싶어서 내뱉는 짧은 주제.이산수학이 맞는지는 모르겠지만... 이것과 연관된 이산수학 문제가 하나 있으니까 이 카테고리에 포스팅하기로 한다. 1. Definition of Beatty Sequence 양의 무리수 rrr에 대해서 Beatty Sequence Br\mathcal{B}_rBr을 다음과 같이 정의한다. Br:={⌊r⌋,⌊2r⌋,⋯ ,⌊nr⌋⋯ } \mathcal{B}_r := \{ \lfloor r \rfloor, \lfloor 2r \rfloor, \cdots, \lfloor nr \rfloor \cdots \} Br:={⌊r⌋,⌊2r⌋,⋯,⌊nr⌋⋯} 2. Rayleigh's theorem 두 양수 무리수 r,sr,sr,s가 1r+1s=1\frac{1}{r}+\frac{1}{s} = 1r1+s1=1을 만족할 때, Br\mathcal{B}_rBr과 \(\ma..
2017.12.15 -
Pépin's test
페르마 수의 primality test에 Miller - Rabin을 쓰면 어떨까? 라는 생각에서 기존 이론을 search하다가 찾아낸 이론인데, 생각해보니 옛날에 배웠던 거다... 그럼 그렇지. Fn=22n+1 is prime⇔3Fn−12≡−1(mod Fn)(n>0) F_n = 2^{2^n} + 1 \text{ is prime} \\ \Leftrightarrow 3^{\frac{F_n-1}{2}} \equiv -1 (\text{mod} \ F_n) (n>0)Fn=22n+1 is prime⇔32Fn−1≡−1(mod Fn)(n>0) pf)⇒) \Rightarrow) ⇒)by Euler’s Criterion, \text{by Euler's Criterion,} by Euler’s Criterion, 3Fn−1/2≡(3Fn) 3^{{F_n-1}/2} \equiv \left(\frac{3}{F_n}\right) 3Fn−1/2≡(Fn3)이 때 Fn≡2(mod3)F_n \equiv 2 (mod 3)Fn≡2(mod3)이므로 FnF_nFn은 법 3에 대한 이차잉여가 아니다. \(\le..
2017.10.14 -
게러슨 부등식 (Gerretsen's inequality)
게레첸 부등식, 게러첸 부등식이라고 더 많이 알려져 있는 것 같은(...) 이 부등식은 삼각형의 둘레의 절반 s=a+b+c2s = \frac{a+b+c}{2}s=2a+b+c, 내접원의 반지름 rrr, 외접원의 반지름 RRR에 관련된 가장 tight한 부등식 중 하나이다. 아마 경시 수준에서 쓰이는 기하부등식 중에선 가장 강한 것 같다. 소개할 증명에서도 상당히 강력한 부등식인 Schur 부등식이 사용된다. 16Rr−5r2≤s2≤4R2+4Rr+3r2 16Rr - 5r^2 \le s^2 \le 4R^2 + 4Rr + 3r^2 16Rr−5r2≤s2≤4R2+4Rr+3r2 (1) Lower bound 클래식한 방법은 부담이 너무 심해서 Lemma를 하나 도입해보았다. x:=s−a,y:=s−b,z:=s−c x := s-a, y := s-b, z := s-cx:=s−a,y:=s−b,z:=s−c Lemma : xy+yz+zx=4Rr+r2\text{Lemma : } xy+yz+zx = 4Rr+r^2Lemma : xy+yz+zx=4Rr+r2 \(..
2017.10.13 -
고정점으로 함방 풀기 - 예시
Find all continuous function f : R→R s.t. ∀x∈R f(f(x))=cosx \text{Find all continuous function } f \ : \ \mathbb{R} \to \mathbb{R} \text{ s.t. } \\ \forall x \in \mathbb{R} \ \ f(f(x)) = cos x Find all continuous function f : R→R s.t. ∀x∈R f(f(x))=cosx 페이스북에서 본 흥미로운 문제인데, 굉장히 기교를 많이 필요로 할 것 같지만 의외로 풀이가 원론적이었다. 당연히 내가 풀진 못했고... 조건을 만족하는 fff가 존재한다고 가정하면,우변인 cosx\text{cos}xcosx 는 단 하나의 고정점(fixed point)을 갖기 때문에, (cost=t\text{cos} t = tcost=t를 만족하는 점, t≈0.7391t \approx 0.7391 t≈0.7391 )이는 fff의 유일한 고정점이어야 한다. 간단히 설명하자면 ttt 이외의 고정점..
2017.10.10 -
#001. ArithMetic - Geometric Mean (AGM) (1)
*이 글은 산술-기하 평균부등식과 관련된 글이 아닙니다. 양의 실수 x>yx>yx>y의 AGM AGM(x,y)AGM(x,y)AGM(x,y)는 다음 두 수열의 극한값으로 정의된다.a0=x, g0=ya_0 = x, \ g_0 = ya0=x, g0=yan+1=an+gn2,gn+1=angna_{n+1} = \frac{a_n+g_n}{2}, g_{n+1}=\sqrt{a_ng_n}an+1=2an+gn,gn+1=angnlimn→∞an=limn→∞gn=AGM(x,y)\lim_{n\to \infty}a_n = \lim_{n\to\infty}g_n = AGM(x,y)limn→∞an=limn→∞gn=AGM(x,y) 1. Proof Of Existence {gn}\{g_n\}{gn}이 수렴함은 단조수렴정리에 의해 자명하다. gng_ngn의 극한값을 ggg라고 두자. 그렇다면 an=gn+12gna_n = \frac{g_{n+1}^2}{g_n}an=gngn+12이므로 극한값은 역시 동일한 ggg가 된다. ■\blacksquare■ 2. Closed Form..
2017.09.13 -
소수의 sum-of-square 표현은 존재한다면 유일하다!
stackexchange에서 본 내용. 페르마의 두 제곱수 정리에 의해, 4k+14k+14k+1꼴의 소수는 두 제곱수의 합으로 표현이 가능하다. 이번엔 그 표현이 유일함을 보이자.기본적으로 꼴은 귀류. 1. Algebraic(?) NTp=a2+b2=c2+d2p = a^2 + b^2 = c^2 + d^2 p=a2+b2=c2+d2으로 표현될 수 있다고 하자. ({a,b}≠{c,d}\{a,b\}\neq\{c,d\}{a,b}={c,d}) 그럼 다음과 같이 ppp는 최소 4개의 서로 다른 가우스 소인수를 가진다. p=(a+bi)(a−bi)=(c+di)(c−di)p = (a+bi)(a-bi) = (c+di)(c-di) p=(a+bi)(a−bi)=(c+di)(c−di)그런데 가우스 정수의 집합 Z[i]Z[i]Z[i]는 Unique Factorization Domain이기 때문에,(*소인수 분해 꼴이 유일한 집합인 것 같다. 머수ㅡ알못이라 한참 후에야 추가가 가능할 듯하다) 이는 \(a..
2017.08.15