整数計画問題におけるグレブナー基底の理論的および実践的有効性

Gröbner 基在整数规划问题中的理论和实践有效性

基本信息

批准号：
15740024
负责人：
大杉英史
金额：
$ 1.86万
依托单位：
Rikkyo University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2005
项目状态：
已结题

项目摘要

本年度の研究では,当該課題の主要な研究対象である,トーリック環,トーリックイデアルを中心に,整数計画問題に関連する,compressed多面体,分割表の解析に関連するトーリック環,符号理論へのグレブナー基底への応用に現れるイデアルについて研究した。以下,それぞれの詳細について述べる。第一に,トーリック環,トーリックイデアルについて,昨年度の研究成果を発展させ,compressed(すなわち,任意の逆辞書式三角形分割が単模)な整凸多面体がspecial simplexを持つことと,付随するトーリック環がGorensteinであることは同値であることを証明した。与えられた凸多面体の頂点を頂点集合とする単体が,special simplexであるとは,元の凸多面体の任意のファセットが,その単体の頂点集合を,1頂点を除いて全て含むときにいう。系として,Christos Athanasiadisの定理「compressedな整凸多面体にspecial simplexが存在するならば,そのトーリック環のh列はある単体的凸多面体のh列と一致する」を使うと,compressedな多面体に付随するGorensteinトーリック環のh列は単峰数列であることが分かる。(なお,この結果はAthanasiadis氏も独立に得ている。)第二に,統計学における分割表の解析に用いられるトーリック環について研究し,それらの正規性や単模性について結果を得た。また,第三に,符号理論へのグレブナー基底による応用に現れるヒルベルトイデアルについて,特に交代群のヒルベルトイデアルの普遍グレブナー基底を求めた。系として,Larry Smithが証明した,対称群のヒルベルトイデアルと交代群のヒルベルトイデアルが一致するための必要十分条件(体の標数が交代群の位数を割り切る)が得られる。

今年的研究重点介绍了这个问题的主要主题，复合环和复曲式的理想，并研究了在压缩多面体和偶然表分析中出现的理想，这些理想与压缩多面体和偶然表的分析以及Grebner对Grebner对代码理论的应用有关。每个细节将在下面说明。首先，我们从去年开发了有关复曲环和复曲面理想的研究结果，并证明了压缩（即任意的逆词法三角剖分）多面体具有特殊的单纯形状，并且随附的曲折环是戈伦斯坦（Gorenstein）是等效的。一个具有给定凸多面体的顶点的单个实体作为顶点集是一种特殊的单纯形，它是指原始凸多面体的任何方面都包含除一个顶点外的所有顶点集的所有顶点集。作为一个系统，Christos Athanasiadis的定理“如果在压缩的凸多面体中有特殊的单纯形，那么圆环环的h序列与单个凸多面体的H序列相吻合，”我们可以看到，戈伦斯坦圆环环的H序列与压缩的多面体序列相关。（该结果是由Athanasiadis独立获得的。）其次，我们研究了用于分析统计表偶然表中的感谢您的环，并获得了其正态性和单肌的结果。第三，我们确定了希尔伯特理想的普遍基础，这些基础是格雷伯纳在代码理论中的应用中，尤其是交替群体的希尔伯特理想。作为一个系统，我们获得了拉里·史密斯（Larry Smith）所证明的必要和充分条件（域的数量分配了交替群体的顺序），对于对称组的希尔伯特（Hilbert）理想，以匹配对称群体的希尔伯特理想。