Rado Numbers and SAT Computations Yuan Chang1 Jes us A. De Loera1 and William J. Wesley1 1Department of Mathematics University of California Davis 1 Shields Ave

2025-05-01 0 0 397.27KB 20 页 10玖币

侵权投诉

Rado Numbers and SAT Computations

Yuan Chang1, Jes´us A. De Loera†1, and William J. Wesley‡1

1Department of Mathematics, University of California, Davis, 1 Shields Ave,

Davis, CA 95616

October 10, 2022

1 Introduction

A well-known result in arithmetic Ramsey theory is Schur’s theorem, which states that for

any k≥1, there is an integer nsuch that every k-coloring of [n] := {1,2,3, . . . , n}induces

a monochromatic solution to x+y=z[24]. The Schur number S(k) is the smallest such n

with this property. It is very diﬃcult to compute S(k) and the largest known Schur number

is S(5) = 161, which was computed in 2018 using SAT solving techniques and created great

attention with its massive parallel computation [15]. In this paper we follow this symbolic

approach to investigate natural variations of Schur numbers.

The Rado numbers are a generalization of Schur numbers, and are of great importance

in arithmetic Ramsey theory (see [12, 17, 19] and the references below). For a given linear

equation E, the k-color Rado number Rk(E) is the smallest number nsuch that every k-

coloring of [n] induces a monochromatic solution to E, or inﬁnity if there is a k-coloring of

Nwith no monochromatic solution to E. Many 2-color Rado numbers for various types of

equations have been computed in, for example, [16,18,21,23]. Explicit formulas for the Rado

numbers R2(a(x−y) = bz) and R2(a(x+y) = bz) are given in [17] and [13]. However, no

such formula is known for the general case R2(ax +by =cz). There are some computations

of 3-color Rado numbers scattered throughout the literature [18, 20, 22], but Rado numbers

with more than two colors have not been studied as often. We present a systematic study

of these numbers.

Another interesting family of numbers is the generalized Schur numbers S(m, k) =

Rk(x1+··· +xm−1=xm). In [4] it was shown that S(m, 3) ≥m3−m2−m−1, and

it was conjectured in [1] and later proved in [8] that S(m, 3) = m3−m2−m−1. Myers

showed in [18] that the numbers Rk(x−y= (m−2)z) give an upper bound for S(m, k), and

several more values of Rk(x−y= (m−2)z) were shown to be equal to S(m, k), thus giving

∗merchang@ucdavis.edu

†deloera@math.ucdavis.edu

‡wjwesley@math.ucdavis.edu

arXiv:2210.03262v1 [math.CO] 7 Oct 2022

exact values for more generalized Schur numbers. Myers went on to make the following

conjecture in [18].

Conjecture 1.1 (Myers).R3(x−y= (m−2)z) = m3−m2−m−1for m≥3.

In this paper we focus on computing Rado numbers for three variable linear homogeneous

equations using SAT-based methods described in Section 2. The main contributions of this

paper are exact formulas for several families of 3-color Rado numbers. In particular, we show

Conjecture 1.1 is true.

Theorem 1.2. The values of the following Rado numbers are known:

1. R3(x−y= (m−2)z) = m3−m2−m−1for m≥3.

2. R3(a(x−y) = (a−1)z) = a3+ (a−1)2for a≥3.

3. R3(a(x−y) = bz) = a3for b≥1,a≥b+ 2,gcd(a, b) = 1.

As a corollary, we obtain the result in [8], an exact formula for the 3-color generalized

Schur numbers.

Corollary 1.2.1. S(m, 3) = m3−m2−m−1for m≥1.

We also compute exactly several 3-color and 4-color Rado numbers.

Theorem 1.3. The values of the following Rado numbers are known.

1. R3(a(x−y) = bz)for 1≤a, b ≤15.

2. R3(a(x+y) = bz)for 1≤a, b ≤10.

3. R3(ax +by =cz)for 1≤a, b, c ≤6.

4. R4(x−y=az)for 1≤a≤4.

5. R4(a(x−y) = z)for 1≤a≤5.

We collect the 3-color Rado number values we computed in Theorem 1.3 in Tables 1 to

8. We also give the additional values R3(ax +ay =bz) for 3 ≤a≤6,11 ≤b≤20 as well

as our values for R4(a(x−y) = bz) in the Appendix (Tables 9 and 10). Underlined entries

in these tables correspond to equations whose coeﬃcients are not coprime.

If the number Rk(E) is ﬁnite for a ﬁxed k, we say that the equation Eis k-regular. If

Eis k-regular for all k≥1, we say Eis regular. In its simplest version, Rado’s classical

theorem gives necessary and suﬃcient conditions for when a linear homogeneous equation is

regular [19].

Theorem 1.4 (Rado).A linear equation Pm

i=1 cixi= 0 with ci∈Zis regular if and only if

there exists a nonempty subset of the cithat sums to zero.

Table 1: 3-color Rado numbers R3(a(x−y) = bz)

a1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 14 14 27 64 125 216 343 512 729 1000 1331 1728 2197 2744 3375

2 43 14 31 14 125 27 343 64 729 125 1331 216 2197 343 3375

3 94 61 14 73 125 14 343 512 27 1000 1331 64 2197 2744 125

4 173 43 109 14 141 31 343 14 729 125 1331 27 2197 343 3375

5 286 181 186 180 14 241 343 512 729 14 1331 1728 2197 2744 27

6 439 94 43 61 300 14 379 73 31 125 1331 14 2197 343 125

7 638 428 442 456 470 462 14 561 729 1000 1331 1728 2197 14 3375

8 889 173 633 43 665 109 644 14 793 141 1331 31 2197 343 3375

9 1198 856 94 892 910 61 896 896 14 1081 1331 73 2197 2744 125

10 1571 286 1171 181 43 186 1190 180 1206 14 1431 241 2197 343 31

11 2014 1508 1530 1552 1574 1596 1618 1584 1575 1580 14 1849 2197 2744 3375

12 2533 439 173 94 2005 43 2053 61 109 300 2024 14 2341 379 141

13 3134 2432 2458 2484 2510 2536 2562 2588 2574 2530 2541 2544 14 2913 3375

14 3823 638 3039 428 3095 442 43 456 3207 470 3113 462 3146 14 3571

15 4606 3676 286 3736 94 181 3826 3856 186 61 3795 180 3835 3836 14

Table 2: 3-color Rado numbers R3(a(x+y) = bz)

a1 2 3 4 5 6 7 8 9 10

1 14 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

2 1 14 243 ∞ ∞ ∞ ∞ ∞ ∞ ∞

3 54 54 14 384 2000 ∞ ∞ ∞ ∞ ∞

4∞1 108 14 875 243 4459 ∞ ∞ ∞

5∞105 135 180 14 864 3430 3072 12393 ∞

6∞54 1 54 750 14 3087 384 243 2000

7∞455 336 308 875 756 14 1536 8748 7500

8∞ ∞ 432 1 1000 108 2744 14 8019 875

9∞ ∞ 54 585 1125 54 3087 1224 14 6000

10 ∞ ∞ 1125 105 1 135 3430 180 7290 14

Nonregular equations may have ﬁnite Rado numbers for small k. The largest kfor

which an equation Eis k-regular is the degree of regularity of E, denoted dor(E). We set

dor(E) := ∞if Eis regular. Rado also proved a theorem that characterized the 2-regular

linear homogeneous equations in three or more variables.

Theorem 1.5 (Rado).Let m≥3and a1, . . . , am∈Z\{0}.Then the equation Pm

i=1 aixi= 0

is 2-regular if and only if there exists iand jsuch that ai>0and aj<0.

For 3 ≤k < ∞, there is no known characterization of the k-regular equations. In [2]

it was shown that for every k, there exists a linear homogeneous equation in k+ 1 vari-

ables that has degree of regularity k. However, for a ﬁxed number of variables, the question

of what degrees of regularity are possible for homogeneous linear equations remains largely

unanswered. Rado made the following conjecture about this question in his Ph.D. thesis [19].

Table 3: R3(ax +by =z)

a1 2 3 4 5 6

1 14 43 94 173 286 439

2∞1093 ∞2975 4422

3∞ ∞ ∞ ∞

4∞ ∞ ∞

5∞ ∞

6∞

Table 4: R3(ax +by = 2z)

a1 2 3 4 5 6

1 1 14 54 ∞70 126

2 14 61 43 181 94

3 243 ∞395 648

4∞∞1093

5∞ ∞

6∞

Table 5: R3(ax +by = 3z)

a1 2 3 4 5 6

1 54 1 27 54 89 195

2 54 31 ∞140 108

3 14 109 186 43

4 384 220 ∞

5 2000 1074

6∞

Table 6: R3(ax +by = 4z)

a1 2 3 4 5 6

1∞ ∞ 1 64 100 ∞

2 1 ∞14 ∞54

3 108 73 105 ∞

4 14 180 61

5 141 ∞

6 31

Table 7: R3(ax +by = 5z)

a123456

1∞45 60 1 125 150

2 105 1 ∞125 70

3 135 100 125 108

4 180 141 ∞

5 14 300

6 864

Table 8: R3(ax +by = 6z)

a1 2 3 4 5 6

1∞40 81 ∞1 216

2 54 81 1 90 27

3 1 ∞135 14

4 54 ∞31

5 750 241

6 14

Conjecture 1.6 (Rado’s Boundedness Conjecture).For all m≥1, there is a number ∆(m)

such that if a linear equation in mvariables is ∆(m)-regular, then it is regular.

In [10] it was shown that Rado’s boundedness conjecture is true if it is true for the

case of homogeneous equations. Those authors also proved the ﬁrst nontrivial case of the

conjecture by showing that if a linear homogeneous equation in three variables is 24-regular,

then it is regular. However, it is not known if 24 is the best possible bound. There are no

known examples of a nonregular linear homogeneous equation in three variables that is 4-

regular. Moreover, in [10], several coloring lemmas give more precise bounds on the degree of

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

RadoNumbersandSATComputationsYuanChang1,JesusA.DeLoera1,andWilliamJ.Wesley11DepartmentofMathematics,UniversityofCalifornia,Davis,1ShieldsAve,Davis,CA95616October10,20221IntroductionAwell-knownresultinarithmeticRamseytheoryisSchur'stheorem,whichstatesthatforanyk1,thereisanintegernsuchthateveryk-c...

展开>> 收起<<

Rado Numbers and SAT Computations Yuan Chang1 Jes us A. De Loera1 and William J. Wesley1 1Department of Mathematics University of California Davis 1 Shields Ave.pdf

共20页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Rado Numbers and SAT Computations Yuan Chang1 Jes us A. De Loera1 and William J. Wesley1 1Department of Mathematics University of California Davis 1 Shields Ave

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: