「計算」の視点から見る数学的難問

本研究は，数学分野において長く未解決となっている様々な難問を，「計算」の視点から捉え直すことで，その困難さを解明し，あるいは，解決への糸口を得ようとするものである．これへ向けて，今年度は，特に以下の２点について成果を得ることができた．１．与えられた自然数を，数値の1と，加算，乗算，および，括弧を任意に用いて表現するときの，数値1の使用回数の最小値を，その数の整数複雑さと呼ぶ．1950年代に提唱されたこの問題は，そのシンプルさにも関わらず，良い上界，あるいは，下界を求めることは長年の未解決問題となっている．本研究では，これまで知られる最良の上界と下界が，それぞれ，2進数表現と3進数表現を元にしていることに着目し，2進と3進を任意の順番で使用できるとする，混合2-3進数表現を提案し，この表現を用いた整数複雑さについて解析を行った．その結果，平均的複雑さに対する，これまで知られる最良の上界の改良や，整数複雑さの分布についての新たな知見を得ることに成功した．この結果は，国際会議ISAAC2022において発表を行った．２．論理関数の重要な表現手法の一つである，多項式しきい値表現の複雑さに関する解析を行った．特に，ODD-MAXBIT関数と呼ばれる論理関数を，この形式で表現したときの，係数の絶対値の和に対する下界を求める問題に対して，既知の最良の上界とほぼマッチする下界を証明することに成功した．これは，20年来の未解決問題を解決したものである．証明には，ランダム割り当てと，論理関数の自己帰着性を巧妙に組み合わせた手法を用いており，より広く決定リストの表現長の解明への発展も期待できる．この結果は，電子情報通信学会論文誌に掲載された．これらに加えて，最疎充填問題等いくつかの離散数理的問題に対して興味深い進展が得られるなど，本研究の目的の達成に向けて重要な進展を得ることができた．

本研究は，数学分野において長く未解決となっている様々な難問を，「計算」の視点から捉え直すことで，その困難さを解明し，あるいは，解決への糸口を得ようとするものである．これへ向けて，今年度は，特に以下の２点について成果を得ることができた．１．与えられた自然数を，数値の1と，加算，乗算，および，括弧を任意に用いて表現するときの，数値1の使用回数の最小値を，その数の整数複雑さと呼ぶ．1950年代に提唱されたこの問題は，そのシンプルさにも関わらず，良い上界，あるいは，下界を求めることは長年の未解決問題となっている．本研究では，これまで知られる最良の上界と下界が，それぞれ，2進数表現と3進数表現を元にしていることに着目し，2進と3進を任意の順番で使用できるとする，混合2-3進数表現を提案し，この表現を用いた整数複雑さについて解析を行った．その結果，平均的複雑さに対する，これまで知られる最良の上界の改良や，整数複雑さの分布についての新たな知見を得ることに成功した．この結果は，国際会議ISAAC2022において発表を行った．２．論理関数の重要な表現手法の一つである，多項式しきい値表現の複雑さに関する解析を行った．特に，ODD-MAXBIT関数と呼ばれる論理関数を，この形式で表現したときの，係数の絶対値の和に対する下界を求める問題に対して，既知の最良の上界とほぼマッチする下界を証明することに成功した．これは，20年来の未解決問題を解決したものである．証明には，ランダム割り当てと，論理関数の自己帰着性を巧妙に組み合わせた手法を用いており，より広く決定リストの表現長の解明への発展も期待できる．この結果は，電子情報通信学会論文誌に掲載された．これらに加えて，最疎充填問題等いくつかの離散数理的問題に対して興味深い進展が得られるなど，本研究の目的の達成に向けて重要な進展を得ることができた．