그뢰브너 기저와 거유 제5화

원문

 『그뢰브너 기저로 거짓을 간파하다』

 거짓말 탐지기란 이름 그대로 거짓말을 탐지하는 기계다.

 첩보물 같은 데서 팔에 이상한 줄 같은 걸 달아놓고 맥박 등을 감지해서 거짓말을 하는지 알아내는 기계다.

 그런 게 정말로 있다면 딱 지금 필요하다만.

 "방금 네가 한 대로, 거짓말쟁이 문제는 다항식의 언어로 변환할 수 있어."

 A. "B는 거짓말을 하고 있다." ⇄ x-y+1=0

 B. "C는 거짓말을 하지 않고 있다." ⇄ y-z=0

 C. "A와 B 중 누군가는 거짓말을 하고 있지 않다." ⇄ z-xy=0

 군죠는 내가 쓴 종이를 집어 올리더니 담담히 설명한다.

 "이렇게 다항식으로 된 방정식들이 묶여있는 걸 보면 아무리 둔감한 너라도 이게 뭔지 알 수 있겠지."

 "아아... 연립방정식이구만."

 "따라서?"
 "그뢰브너 기저로 풀 수 있다......그건가."

 내 대답에 군죠가 살짝 미소를 띤다.

 "아, 다만 주의해야 되는 게 있어. 우리는 0과 1 뿐인 세계에서 그뢰브너 기저를 계산할거야."

 우리가 일상 생활에서 계산을 할 때 어느 수에서 계산하는 지는 그렇게 의식하지 않는다.

 슈퍼에서 거스름돈을 계산할 때 "나 지금 유리수 위에서 계산하고 있어!"라고 하는 녀석은 변태다.

 "너도 아는 대로 그뢰브너 기저는 어떤 체에서 계산하냐에 따라 그 모습을 바꾸지."

 지금 군죠가 말한 '체(Field)'란 수학 용어로, 사칙연산이 가능한 수의 집합을 칭한다.

 결코 체로 걸러서 계산을 한다거나 화창한 햇빛 아래 field 위에 앉아 계산을 한다는 뜻이 아니다.

 0과 1만 있는 세계 역시 유리수나 실수처럼 덧셈, 뺄셈, 곱셈, 나눗셈이 가능하니 체다.

 "이번 그뢰브너 기저 계산은 0과 1로 구성된 체, F_2에서 할 거야."

 0과 1로 이루어진 체는 흔히 F_2라 불린다.

 즉, 이제부터 다항식의 계수에 0과 1만 있다 치고 그뢰브너 기저를 계산하려는 것이다.

 이제 계산을 해야 하는데, 음,

 "으음, Mathematica에서는 디폴트로 유리수체에서 계산을 한단 말이지. 그럼 적당히 옵션 추가해서 계산하면 되나......"

 "케이스케, 아쉽지만 나는 Asir파라서 말이야."

 군죠는 그렇게 말하더니 발밑에 있는 가방에서 키보드 중앙에 빨간 버튼이 달린 노트북을 꺼낸다.

 가방 갖고 있었던 거냐.

 "Asir는 일본에서 개발된 수식처리 소프트웨어인데, 다른 대수적 계산은 물론이고 그뢰브너 기저도 계산할 수 있어. 그리고 무엇보다도 공짜지. 이 기회에 너도 Asir로 계산해볼래?"

 "하하, 다음 기회에 할게."

 "그래?"

 "그, 그보다 빨리 계산하자고."

 "그러지 뭐."

 간신히 이야기를 피했다.

 아무래도 이제부터는 군죠 선생님께서 친절하게 알려주시려는 모양이다.

 "계산할 다항식은,"

 x-y+1

 y-z

 z-xy

 "...인데 Asir로 이 그뢰브너 기저를 계산하려면,"

 nd_gr

 "를 쓰면 돼."

 "호오."

 "nd_gr 안에 이렇게 다항식을 넣으면,"

 nd_gr([x-y+1,y-z,z-x*y])

 "이렇게 되지."
 "그런데 이렇게만 해갖고는 계산 안 되지 않아?"

 "서두르지 마, 이 동정아. 이제 사용할 변수를 순서대로 입력하자고."

 nd_gr([x-y+1,y-z,z-x*y],[x,y,z])

 "그리고 다음이 중요해. 이번엔 0과 1뿐인 체 F_2에서 계산할 거니까 표수로는 2를 입력하자."

 nd_gr([x-y+1,y-z,z-x*y],[x,y,z],2)

 여기서 표수(characteristic)란 1을 계속 더해서 0이 되는 횟수다.

 체 F_2에서는 1+1=0이라 1을 두 번 더해서 0이 되므로 표수가 2다.

 "마지막으로 단항식 순서(monomial order)를 정하자. Asir에선 잘 쓰이는 단항식 순서가 번호로 지정되어 있어. 지금은 2:사전식 순서를 쓸 거야. 그러니 오른쪽에 2를 넣자."

 nd_gr([x-y+1,y-z,z-x*y],[x,y,z],2,2)

 "완성이야. 그러면 계산해보자고."

 [0] nd_gr([x-y+1,y-z,z-x*y],[x,y,z],2,2);

 [z^2,y+z,x+z+1]

 군죠가 키보드를 타닥타닥 치며 Asir를 실행했다.

 "됐다. 답 나왔어. 케이스케, 이건 뭔지 알겠어?"

 "아아, 거짓말쟁이 문제에 대응되는 연립방정식을 계산한 결과가,"

 z^2,y+z,x+z+1

 "...라는 것은,"

 z^2=0

 y+z=0

 x+z+1=0

 "...가 해를 구하기 최적인 형태라는 거지?"

 "그렇지. 실제로,"

 x=1

 y=0

 z=0

 "....가 방정식의 해라는 걸 쉽게 알 수 있지."
 "그리고 0이 참, 1이 거짓에 대응되었으니까 이건,"

 A=거짓말쟁이

 B=참말쟁이

 C=참말쟁이

 "라는 뜻인가."
 "네가 처음에 구한 답이랑 똑같지?"
 "......그렇네."

 "이렇게 그뢰브너 기저로 거짓말쟁이 문제를 풀었어."

 Mathematica로 계산해도,

 GroebnerBasis[{x - y + 1, y - z, z - x*y}, {x, y, z}, Modulus -> 2]

 를 입력하면 똑같이 {z^2, y + z, 1 + x + z}가 나온다.

 (참고로 Modulus ->2 가 표수를 2로 지정하고 있다.)

 "흠. 꽤 재밌네. 군죠 네가 이거 생각한 거야?"
 "훗, 뭐, 미국서 들은 수업에서 '논리 계산은 연립방정식 문제로 바꿀 수 있다'길래 거기서 아이디어를 얻은 거야."

 "그 수업 재밌겠다."

 "실제로는 계산 효율도 생각해야겠지만 말이지. 두뇌 체조로는 좋은 문제였지?

 "응, 재밌었어."
 "그리고 말야."

 군죠가 갑자기 꼰 다리를 풀더니 반대로 꼬았다.

 뭐지. 또 화난 건가.

 "다음에 밥이나 한 번 먹을래?"

 "음?"
 "일본에 돌아온 지 얼마 안 돼서 일본 음식이 너무 그립단 말이지. 맛집 아는 데 좀 있으면 알려줘."

 생각치도 못했다. 군죠가 내게 밥 약속이라니 별일이다.

 뭐, 소꿉친구이기도 하니 거절할 이유도 없다.

 "응, 그래. 그럼 이번 일요일 어때?"

 "오, 좋지."
 "그럼 이따 연락할게."

 "......잠깐, 너 폰 바꿨잖아."

 "어, 아. 그렇지."

 "에휴. 바꿨으면 연락 정도는 하라고......"

 작년 폰을 바꿨을 때 유학 중이던 군죠에게는 깜빡하고 폰을 바꿨다고 말하지 못했다.

 그 이후로 군죠하고는 계속 연락 못했었나.

 ......그러고 보니 군죠는 내가 휴학한 걸 어떻게 안 거지?

 "이참에 문자 말고 LINE 쓰는 게 어때?"

 "LINE?"
 "안 깔았어?"
 "아니. 일단 깔긴 했는데 거의 안 써서."

 나는 친구가 적어서 LINE 친구 리스트에 가족과 지인 몇 명 말고는 없다.

 어쩌면 반톡같은 데엔 들어있을 지도 모르겠다. 아니, 없기를 바란다.

 "자, 그럼 아이디 교환하자고."

 "으음, 뭘 눌러야 하더라...... 이거?"
 "아니잖아. 이거 말고 저거."
 "어떤 건데."
 "그러니까, 그거..."

 "그건 Boolean Gröbner Basis야."

 갑작스런 일이었다.

 등 뒤에서 들린 정체불명의 목소리가 우리의 대화를 가로막았다.

 그리고 나는 살해당했다.