An Algorithmic Approach to Constructing Sets with Distinct Subset Sums

Abstract

이 논문에서는 Erdös의 풀리지 않은 문제 중 하나인 distinct subset sums 문제를 다룬다. 언급된 문제와 관련하여 가장 잘 알려져 있는 예시는 Conway-Guy 수열로, 이는 Conway와 Guy에 의해서 1967년에 발견되었으며, 이 수열에 의해 서 만들어진 특정 집합들이 문제의 예제로 적용이 될 수 있음과 그에 따라 문제의 해답에 대한 상계로 쓰일 수 있음은 1996년에 와서야 Bohman에 의해 증명이 되었다.

위의 증명을 포함한 가장 대표적으로 알려져 있는 연구결과는 Lunnon과 Bohman에 의해 이루어져 있으나, 이는 어디까지나 지극히 산술적인 결과에 의한 것이며, 이는 직관의 부재로 연결되어 원래의 문제와의 인위적인 연관성에 대 하여 불만이 서술되어왔다.

따라서 Conway-Guy 수열의 구조적인 형태를 알아보기 위해 distinct subset sums 문제를 다른 방향에서 알고리즘적으로 접근하여 Conway-Guy가 자연적으로 도출이 됨을 설명하고자 시도하였다.

A version of the distinct subset sums problem, also referred to as the sum packing problem, is formulated as follows:

What is the smallest integer m such that there exists a set of positive integers A of size n where all subsets have distinct sums and all elements do not exceed m?

This is one of the numerous unsolved problems that was asked by Erdos, originally in 1931. In 1967, Conway and Guy gave a now well known sequence of integers for m and conjectured that the sets derived from this sequence have distinct subset sums and are optimal. In this dissertation, we attempt an geometrically inspired algorithmic approach for constructing the sets derived from the Conway-Guy sequence.