스스로를 그리는 부등식

\displaystyle \frac{1}{2} < \left\lfloor \text{mod} \left( \left\lfloor \frac{y}{17} \right\rfloor 2^{-17 \lfloor x \rfloor - \text{mod}(\lfloor y \rfloor,17)},2 \right) \right\rfloor

위 부등식의 영역을 그리면 다음과 같이 나타난다. 여기서 \mod (r,n)rn으로 나눈 나머지.

Jeff Tupper의 SIGGRAPH 2001 논문[1]에 등장하여 Tupper’s self referential formula란 이름을 가진 식이다. 부등식의 영역이 해당 부등식 자체로 나타나는 마치 quine같은 결과를 보여주는데, 사실 함정이 하나 있다. 잘 보면 y좌표가 N이란 값에 의존하게 나타나있고 그 값이 명시되어있지 않다는 점인데, 위 그림에서 나오는 N의 값은 다음과 같다.

N=4858450636189713423582095962494202044581400587983244549483093085061934704708809928450644769865524364849997247024915119110411605739177407856919754326571855442057210445735883681829823754139634338225199452191651284348332905131193199953502413758765239264874613394906870130562295813219481113685339535565290850023875092856892694555974281546386510730049106723058933586052544096664351265349363643957125565695936815184334857605266940161251266951421550539554519153785457525756590740540157929001765967965480064427829131488548259914721248506352686630476300

실은 이 부등식의 영역의 그래프는 높이가 17인 모든 도트 그림을 전부 층층이 포함하고 있고, 위 그래프는 전체 그래프에서 x \geq 0, N \leq y \leq N+17인 부분에 대해서만 그린 것으로 그 바깥 부분에도 해당 부등식이 성립하는 영역이 있다. 즉 높이가 17인 임의의 도트 그림에 대해, 그 그림에 해당하는 이진수의 값을 구하고 17을 곱한 값을 N이라 두면, N \leq y \leq N+17인 부분에 대해서 그 그림이 나타나게 된다. 또 다른 예로, N=6064344935827571835614778444061589919313891311에 대해 N \leq y \leq N+17 부분의 영역은 다음과 같이 나온다.

즉 “스스로를 그리는”이란 표현은 사실 어폐가 있는 표현이고, 엄밀히 말하자면 “고정된 높이의 모든 도트그림을 표현할 수 있는” 부등식 정도로 쓸 수 있겠다.

도트 그림을 그려 해당 N을 찾아내거나 N에 해당하는 도트 그림을 그리는 곳들도 있다. Numberphile에서 이 식에 대해서 다루기도 했다.

주어진 식을 조금 뜯어보면 그 원리를 가늠할 수 있다. 먼저 주어진 식은 \lfloor x \rfloor x,\lfloor y \rfloor의 값에만 의존한다는 것을 주목한다. 중간에 \lfloor y/17 \rfloor이란 항이 있지만 \lfloor \frac{\lfloor y \rfloor}{17} \rfloor으로 바꿔쓸 수 있다. 따라서 정수 a,b에 대해 x=a,y=b일 때 부등식이 성립함과 단위정사각형(도트) [a,a+1) \times [b,b+1)이 영역에 포함됨이 동치가 되며, 정수 a,b에 대해

\displaystyle \frac{1}{2} < \left\lfloor \text{mod} \left( \left\lfloor \frac{b}{17} \right\rfloor 2^{-17a - \text{mod}(b,17)},2 \right) \right\rfloor

에 해당되는 경우가 어떻게 나오는지를 생각하면 된다.

a=0, b=17c인 경우를 생각한다. 그러면 \mod(\lfloor b \rfloor,17)=0이므로 주어진 부등식은 \frac{1}{2} < \lfloor \mod(c,2) \rfloor이 된다. 이것은 c가 홀수일 때, 즉 c의 이진법 전개의 끝자리수가 1일 때만 성립한다. 마찬가지로 a=0, b=17c+1이면 주어진 부등식은 lfloor \frac{1}{2} < \lfloor \mod ( \frac{c}{2},2) \rfloor가 된다. \frac{c}{2}의 이진법 전개는 c의 이진법 전개에서 맨 끝에 소수점이 있었다고 할 때 그 소수점을 한 자리 왼쪽으로 shift한 것이므로 \frac{c}{2}를 2로 나눈 mod 값은 소수점 바로 왼쪽 자리수보다도 왼쪽에 있는 자리수들을 없앤 것이 되며, 그 정수부를 구하면 소수점 오른쪽 자리수들이 사라지게 된다. 따라서 이 부등식이 성립하는 것은 c의 이진법 전개의 끝에서 두 번째 자리수가 1일 때가 된다.

마찬가지로 계속해서 a=0, b=17c+16일 때까지를 따지면 c의 이진법 전개의 마지막 17자리를 (마지막 자리부터 읽으면서 아래에서 위로) 시각화한 것이 된다. 예컨대 c마지막 17자리가 11001011001001101이었으면 (a,b)=(0,17c)에 해당하는 도트는 마지막 자리수가 1이므로 해당되어 검게 칠하고, (a,b)=(0,17c+1)에 해당하는 도트는 마지막에서 두 번째 자리수가 0이므로 해당되지 않아 그대로 두고, (a,b)=(0,17c+2)에 해당하는 도트는 마지막에서 세 번째 자리수가 1이므로 해당되어 검게 칠하고… 이런 식.

a=1, b=17c에서 b=17c+16일 때에는 그 다음 17자리를 아까 칠한 17 \times 1 모양의 도트 그림 바로 오른쪽 위치에 시각화하고, 이것이 되풀이되는 것이다.

당연히 17은 특별한 수가 아니며, 해당 도트 그림을 그릴 때에 적절한 높이로 설정한 값일 뿐이다. 따라서 부등식에서 17만 다른 값으로 대체할 수 있으며, 더 큰 값으로 설정하면 더 세밀한 도트 그림을 그릴 수도 있다.

참고로 해당 논문[1]이나 이를 인용한 곳들(위키피디아, 울프람 매스월드 등등)에서는 N을 다음과 같은 값으로 설정하고 있지만, 이 값으로 그림을 그리면 원하는 그림을 180도 회전한 모양이 나온다. 이는 Tupper가 plotting한 환경에서는 x,y축 방향이 일반적으로 상정하는 방향과 달랐기에 생긴 일로 보임.

Source: https://shreevatsa.wordpress.com/2011/04/12/how-does-tuppers-self-referential-formula-work/

블로그 The Lumber Room의 관련 글도 참조.

Elegant Math 계정에서 작성한 트윗 타래를 정리. (2017/06/18)

References

[1] J. Tupper, “Reliable Two-Dimensional Graphing Methodsfor Mathematical Formulae with Two Free Variables” In Procceedings of the ACM Siggraph 2001, 2001. http://www.dgp.toronto.edu/~mooncake/papers/SIGGRAPH2001_Tupper.pdf

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중