Complete local expansion of the availability function in random sequential adsorption of aligned squares at low density: Termination at fourth order

당신이 거대하고 텅 빈 평평한 들판에 똑같은 모양의 정사각형 자동차들을 주차하려고 한다고 상상해 보세요. 당신에게는 엄격한 규칙이 하나 있습니다. 이미 주차된 다른 자동차와 겹치는 곳에는 차를 세울 수 없다는 것입니다. 당신은 자동차를 하나씩 무작위 위치에 주차하며, 더 이상 충돌 없이 차를 세울 수 없을 때까지 이 과정을 반복합니다. 이 과정은 **무작위 순차 흡착(Random Sequential Adsorption, RSA)**이라고 불립니다.

F. Tolea와 M. Tolea의 논문은 이 주차 게임의 초기 단계에 대한 수학적 조사입니다. 그들은 다음을 알고 싶어 했습니다: "들판을 채워 나갈수록, 다음 차를 위해 남은 공간은 얼마나 되는가?"

그들은 이 남은 공간을 **"가용성 함수(availability function)"**라고 부릅니다.

문제: 단순히 빼기만 하면 되는 문제가 아니다

처음에는 수학이 쉬울 것이라고 생각할 수도 있습니다. 만약 자동차 한 대가 특정 영역을 막는다면, 두 대의 자동차는 두 배의 면적을 막아야 하는 게 당연해 보이니까요.

아닙니다. 이것은 마치 투명한 거품들이 있는 테트리스 게임과 같습니다.

• 거품(The Bubble): 자동차를 주차하면, 그 자동차가 차지하는 공간만 막는 것이 아닙니다. 또한 다른 자동차가 주차할 수 없는 주변 영역(배제 영역)을 만들어냅니다. 정사각형 자동차의 경우, 이 금지 구역은 더 큰 정사각형 형태가 됩니다.
• 중첩(The Overlap): 만약 두 대의 자동차를 가깝게 주차하면, 그들의 금지 구역이 서로 겹칠 수 있습니다. 만약 단순히 두 구역의 크기를 더하기만 한다면, 겹쳐진 중간 부분을 중복해서 계산하게 될 것입니다. 따라서 중첩된 부분을 빼주어야 실제 차단된 면적을 구할 수 있습니다.
• 연쇄 반응(The Chain Reaction): 하지만 자동차가 세 대라면, 그들의 구역이 하나의 작은 지점에서 모두 겹칠 수도 있습니다. 만약 두 대씩의 중첩을 빼기만 했다면, 그 세 대가 겹치는 지점을 너무 많이 빼버렸을 수도 있습니다. 그래서 그 부분을 다시 더해주어야 합니다.

저자들은 **포함-배제의 원리(Inclusion-Exclusion)**를 사용합니다. 이것은 마치 방 안에 있는 사람들의 수를 세려는 친구들의 모임과 같습니다. 사람들이 그룹으로 서 있어서 계속 잘못 세게 되는 상황입니다:

1. 모든 사람을 개별적으로 셉니다 (1차/First Order).
2. 두 명씩 짝을 지어 서 있는 사람들을 두 번 셌다는 것을 깨닫고, 그 쌍(pairs)을 뺍니다 (2차/Second Order).
3. 세 명씩 그룹을 지어 있는 사람들을 너무 많이 뺐다는 것을 깨닫고, 다시 더합니다 (3차/Third Order).
4. 네 명의 그룹에서 또 실수를 했다는 것을 깨닫고, 다시 뺍니다 (4차/Fourth Order).

위대한 발견: "마법의 숫자" 4

이 논문의 가장 흥미로운 부분은, 정렬된 정사각형(축에 평행하게 주차된 자동차)의 경우, 이 계산 게임이 정확히 4에서 멈춘다는 것입니다.

저자들은 다음과 같은 기하학적 사실을 증명했습니다: 비중첩 상태로 주차된 자동차들의 "금지 구역"이 동일한 단 하나의 점에서 모두 겹치도록 배치하는 것은 물리적으로 불가능하다는 것입니다. 즉, 5대 이상의 자동차가 이렇게 겹치게 만드는 것은 불가능합니다.

• 1대, 2대, 또는 3대의 자동차의 "금지 구역"이 겹칠 수 있습니다.
• 4대의 자동차의 구역이 겹칠 수도 있습니다.
• 하지만 5대의 자동차가 이렇게 겹치는 것은 불가능합니다.

이러한 기하학적 한계 때문에, "가용 공간"을 구하는 수학적 계산은 무한한 수정 목록을 필요로 하지 않습니다. 네 번째 수정에서 딱 멈추게 됩니다. 저자들은 이 첫 네 단계에 대한 정확한 수치를 계산해 냈습니다.

결과: 완벽한 공식

그들은 들판이 이미 얼마나 채워져 있는지($q$)에 따라 새로운 차를 위한 공간이 얼마나 남는지를 알려주는 특정 공식(다항식)을 도출했습니다.

공식은 다음과 같습니다:
$$\text{가용 공간(Available Space)} = 1 - 4q + 3.5q^2 - 0.88q^3 + 0.059q^4$$

• $1$: 전체 빈 들판.
• $-4q$: 단일 자동차가 차지하는 공간.
• $+3.5q^2$: 두 자동차의 구역이 겹칠 때의 보정값.
• $-0.88q^3$: 세 개의 구역이 겹칠 때의 보정값.
• $+0.059q^4$: 네 개의 구역이 겹칠 때의 최종 보정값.

이 연구가 중요한 이유 (논문에 따르면)

저자들은 이 공식이 "국소적(local)" 관점에서 정확하다고 설명합니다. 이 공식은 자동차들이 서로를 어떻게 막는지에 대한 기하학적 구조를 완벽하게 설명합니다.

하지만 그들은 한계점도 지적했습니다. 이 공식은 들판이 약 34.5% 찼을 때 더 이상 차를 세울 수 없다고 예측합니다. 그러나 실제로 게임을 계속 진행하면, 정말로 꽉 막히기(jammed) 전까지 들판을 약 **56%**까지 채울 수 있습니다.

왜 이런 차이가 발생할까요?
이 공식은 국소적인 중첩(이웃이 이웃을 막는 것)만을 봅니다. 실제 게임에는 전역적인(global) 조직화가 포함됩니다. 들판이 점점 더 꽉 차게 되면, 자동차들은 단순한 국소적 규칙으로는 설명할 수 없는 복잡하고 장거리적인 패턴을 형성하며 배치됩니다. "정체(jamming)" 현상은 바로 이러한 장거리 연결 때문에 발생하는 것이지, 단순히 인접한 이웃 때문이 아닙니다.

요약

간단히 말해, 저자들은 복잡한 기하학 퍼즐을 풀었습니다:

1. 정사각형 자동차를 무작위로 주차할 때 공간이 얼마나 손실되는지 정확히 알아냈습니다.
2. 정사각형의 경우, 네 대의 자동차 그룹까지만 계산하면 완벽한 국소적 답을 얻을 수 있다는 것을 증명했습니다.
3. 이를 위한 정밀한 공식을 만들었는데, 이 공식은 주차 초기 단계에 대한 "완벽한 지도" 역할을 하지만, 실제 주차장이 너무 붐비고 복잡해지면 단순한 국소적 규칙으로는 설명할 수 없는 한계에 부딪히게 됩니다.

그들은 또한 컴퓨터 시뮬레이션을 통해 자신들의 수학적 계산을 재검증했으며, 수치가 완벽하게 일치함을 확인했습니다.