Studien zur Kombinatorik. (Q2624303)

Ein System von Gleichungen oder sonstigen Bedingungen für die Variablen \(x_1, x_2,\dots, x_n\) nennt Verf. \(k\)-fach regulär, wenn bei jeder möglichen Verteilung der positiven ganzen Zahlen auf \(k\) Klassen es stets mindestens eine Klasse gibt, derart, daß Zahlen \(a_1, a_2,\dots,a_n\) dieser Klasse für \(x_\nu =a_\nu \) \((\nu =1,2,\dots, n)\) die Bedingungen des Systems erfüllen. Ein System, das \(k\)-fach regulär für jedes \(k\) ist, nennt Verf. regulär. Man braucht hierbei nicht alle positiven ganzen Zahlen auf die Klassen zu verteilen; denn Verf. zeigt, daß, wenn ein System \(k\)-fach regulär bei Verteilung aller positiven ganzen Zahlen ist, sich stets eine nur vom System abhängende Schranke \(C\) angeben läßt, derart, daß das System noch \(k\)-fach regulär bleibt, wenn zu den Bedingungen des Systems noch \(x_\nu \leqq C\) für alle \(\nu \) hinzukommt. Für die Regularität von Systemen waren bisher nur ganz spezielle Resultate bekannt. \textit{I. Schur} hatte gezeigt [Deutsche Math. Ver. 25, 114--117 (1916; JFM 46.0193.02)], daß in der Bezeichnungsweise des Verf. die Gleichung \[ x_1 - x_2 = x_3 \] reguär ist, genauer, daß schon bei jeder Verteilung der ganzen Zahlen \(1,2,\dots, [e\cdot k!]\) auf \(k\) Klassen mindestens eine Klasse zwei zugleich mit ihrer Differenz enthält. Der Satz von \textit{B. L. van der Waerden} [Nieuw Arch. Wisk. (2) 15, 212--216 (1927; JFM 53.0073.12)], daß für jedes \(k\) und \(l\) sich eine nur von \(k\) und \(l\) abhängende Schranke \(W(k,l)\) angeben läßt, derart, daß bei jeder Verteilung der Zahlen \(1,2,\dots, W(k,l)\) auf \(k\) Klassen mindestens eine Klasse eine Progression von \(l\) Gliedern enthält, bedeutet also, daß das System \[ \begin{gathered} x_2 - x_1 = x_3 - x_2 =\dots = x_{l-1} - x_{l-2} = x_l - x_{l-1} \neq 0,\\ x_\nu \leqq W(k,l)\qquad (\nu =1,2,\dots,l), \end{gathered} \] \(k\)-fach regulär ist. Dieser Satz wird in der Arbeit wesentlich benutzt; Verf. gibt für ihn einen etwas abgeänderten Beweis. \textit{I. Schur} hatte (siehe \textit{A. Brauer} [Über Sequenzen von Potenzresten. Sitzungsber. Akad. Berlin 1928, 9--16 (1928; JFM 54.0169.02)]) diesen Satz dahin verallgemeinert, daß sich eine Schranke \(W_1(k,l)\) angeben läßt, derart bei jeder Verteilung der Zahlen \(1,2,\dots, W_1(k,l)\) auf \(k\) Klassen mindestens eine Klasse eine Progression von \(l\) Gliedern und zugleich die Differenz der Progression enthält. Verf. verallgemeinert dies auf Grund seiner unten angegebenen Kriterien dahin, daß für jedes \(k,l,r\) sich eine Konstante \(W_2(k,l,r)\) angeben läßt, daß bei jeder Verteilung der Zahlen \(1,2,\dots,W_2(k,l,r)\) auf \(k\) Klassen mindestens eine Klasse eine arithmetische Reihe \(r\)-ter Stufe von \(l\) Gliedern zugleich mit allen Differenzen bis zur Stufe enthält. Daß für jedes positive \(a\) die Gleichung \[ x_1 + ax_2 - x_3 = 0 \] regulär ist, hatte Ref. [Sitzungsber. Akad. Berlin 1931, 329--341 (1931; JFM 57.0188.03)] gezeigt. Verf. zeigt, daß die ähnliche Gleichung \[ x_1 + x_2 - ax_3 = 0 \] im allgemeinen nicht mehr regulär ist. Er beweist das folgende allgemeine Kriterium: Dann und nur dann ist die lineare homogene Gleichung mit rationalen Koeffizienten \[ a_1x_1 + a_2x_2 + \dots a_nx_n = 0 \qquad (a_\nu \neq 0) \] regulär, wenn irgendwelche der \(a_\nu \) eine verschwindende Summe haben. Allgemein wird gezeigt: Dann und nur dann ist das lineare homogene Gleichungssystem mit rationalen Koeffizienten \(a_{\mu \nu }\), \[ \sum _{\nu =1}^n a_{\mu \nu } x_\nu = 0 \qquad (1\leqq \mu \leqq m), \] regulär, wenn die Matrix \((a_{\mu \nu })\) die folgende Eigenschaft hat: Bei geeigneter Numerierung lassen sich die Spalten so in Gruppen \(G_1, G_2,\dots, G_t\) einteilen, daß die Summe der Spalten von \(G_1\) verschwindet und für jedes \(\tau = 2,3,\dots, t\) die Summe der Spalten von \(G_\tau \) eine lineare Kombination der Spalten von \(G_1, G_2,\dots,G_{\tau -1}\) ist. Ähnliche Kriterien werden für die inhomogenen linearen Gleichungssysteme aufgestellt, ferner für den Fall, daß die Koeffizienten beliebige Zahlen sind, und für den Fall, daß nicht nur die positiven, sondern auch die negativen ganzen Zahlen auf Klassen verteilt werden. Ferner wird gezeigt, daß bei jeder Verteilung der positiven ganzen Zahlen mindestens eine Klasse existiert, in der sämtliche überhaupt existierenden regulären linearen homogenen Gleichungssysteme mmindestens eine Lösung haben. Für \(k\)-fache Regularitët erhält Verf. einige spezielle Sätze. So ist z. B. die Gleichung \[ c (x+y) = z \] höchstens dreifach regulär, falls \(c\) rational, aber keine Potenz von \(2\) ist, ist \(c=2^\alpha \) (\(\alpha \) ganz), so ist die Gleichung entweder regulär oder höchstens fünffach regulär. Ferner werden alle linearen homogenen Gleichungen bestimmt, die zweifach regulär sind. Schließlich überträgt Verf. einen Teil seiner Resultate auf die Regularität von Komplexen; hierbei wird unter einem Komplex eine Menge verstanden, deren Elemente endliche Teilmengen der Menge \(\mathfrak Z\) aller natürlichen Zahlen sind. Ein Komplex \(\mathfrak C\) \(k\)-fach regulär, wenn es bei jeder Zerlegung von \(\mathfrak Z\) in \(k\) Teilmengen immer mindestens eine unter diesen Teilmengen gibt, in der ein Element von \(\mathfrak C\) enthalten ist. Bei den Komplexen können die natürlichen Zahlen auch durch die Elemente einer abstrakten abzählbaren Menge ersetzt werden. (III 6.)