ON FROBENIUS FORMULAS OF POWER SEQUENCES FEIHU LIU1AND GUOCE XIN2 Abstract. LetA a1 a2 . . . a n be a sequence of relative prime integers each greater

2025-05-02 0 0 475.16KB 16 页 10玖币

侵权投诉

ON FROBENIUS FORMULAS OF POWER SEQUENCES

FEIHU LIU1AND GUOCE XIN2,∗

Abstract. Let A= (a1, a2, . . . , an) be a sequence of relative prime integers, each greater

than or equal to 2. The Frobenius number g(A) represents the largest integer that cannot

be expressed as a nonnegative linear combination of the elements in A. Our recent work has

introduced a combinatorial method for calculating g(A) in the speciﬁc form A= (a, a +B) =

(a, a +b1, . . . , a +bk). This method reduces the problem to a simpler optimization problem,

denoted as OB(M). In this paper, we apply this method to solve the open problem of charac-

terizing g(A) for the square sequence A= (a, a + 1, a + 22, . . . , a +k2). We demonstrate that

the Frobenius number g(a, a + 12, a + 22, . . .) for the inﬁnite square sequence admits a simpler

solution. This is because the corresponding optimization problem, OB(M), can be solved by

applying number-theoretic principles, speciﬁcally Lagrange’s Four-Square Theorem and re-

lated results. Consequently, we are able to resolve the open problem by utilizing Lagrange’s

Four-Square Theorem in conjunction with generating functions.

Mathematic subject classiﬁcation: Primary 11D07; Secondary 05A15, 11B75, 11D04.

Keywords: Diophantine problem; Frobenius number; Four-Square Theorem; Generating function.

1. Introduction

Let A= (a1, a2, . . . , an) be a sequence of relative prime integers, each greater than or

equal to 2. The Frobenius number g(A) is the largest integer that cannot be expressed as a

nonnegative linear combination of the elements in A. The determination of g(A) has been

the subject of extensive research. For an exhaustive treatment of the subject, see [13]. When

n= 2, Sylvester [19, 20] derived the formula g(a1, a2) = a1a2−a1−a2in 1882. For n= 3, a

formula involving rational functions was introduced by Denham [3], and further investigated

by Tripathi [22]. However, for n≥4, a general formula for g(A) remains elusive, although

numerous special cases have been resolved (cf. [1, 4, 8, 15, 18, 21]). Computational approaches

to the Frobenius number have been explored by Kannan [9] and Ramrez Alfonsn [12].

Our main objective is to address an open problem posed by Einstein, Lichtblau, Strzebon-

ski, and Wagon [5]. This problem concerns the characterization of g(A) for the square sequence

A= (a, a+12, a+22, . . . , a+k2). In 2007, these authors analyzed the cases k∈ {1,2,3,4,5,6,7}

using geometric algorithms and conjectured that the Frobenius number for this sequence ad-

mits a formula of the form 1

k2(a2+ca)−d, where cand dare integers dependent on kand the

residue class of amodulo k2.

We validate this conjecture by employing the combinatorial method introduced by Liu-Xin

[10], drawing upon Lagrange’s “Four-Square Theorem” from Number Theory.

Date: June 26, 2024.

∗This work was partially supported by NSFC(12071311).

arXiv:2210.02722v3 [math.CO] 26 Jun 2024

2 FEIHU LIU1AND GUOCE XIN2,∗

To this end, we need to introduce some essential notation and results from [10]. Through-

out this paper, we denote the sets of all integers, non-negative integers, and positive integers

by Z,N, and P, respectively.

A key result due to Brauer and Shockley, which is widely used, is as follows.

Theorem 1.1 ([2]).Consider A:= (a, B)=(a, b1, b2, . . . , bk)with gcd(A)=1,d∈P, and

gcd(a, d) = 1. Let Rrepresent the set nax +Pk

i=1 bixi|x, xi∈Noand Nr:= Nr(a, B) =

min{a0|a0≡rmod a, a0∈ R}. Then the Frobenius number is given by

g(A) = g(a, B) = max

r∈{0,1,...,a−1}{Nr} − a= max

r∈{0,1,...,a−1}{Ndr} − a.

Let A= (a, ha +dB)=(a, ha +db1, . . . , ha +dbk). The computation of Ndr is reduced to

a minimization problem deﬁned by

OB(M) := min (k

i=1

xi|

i=1

bixi=M, xi∈N,1≤i≤k).

Lemma 1.2 ([10]).Let A= (a, ha +db1, . . . , ha +dbk),k, h, d, bi∈Pand gcd(A)=1. For a

given 0≤r≤a−1, we have

Ndr = min{Ndr(m)|m∈N},where Ndr(m) := {OB(ma +r)·ha + (ma +r)d}.(1)

The lemma holds when ktends to inﬁnity. See Lemma 2.7 for instance.

The Four-Square Theorem enters our analysis when we consider the inﬁnite square se-

quence, i.e., g(A′), where A′= (a, a +B′)=(a, a + 12, a + 22, . . .). The optimization problem

OB′(M) is ideally solved by Number Theorists, in terms of the Four-Square Theorem and

related results. Consequently, we are able to determine g(A′). Similarly, we are able to deter-

mine g(A′) for the prime sequence A′= (a, a + 1, a +p1, a +p2, . . .), where (p1, p2, . . .) is the

prime sequence (2,3,5,7, . . .).

The ﬁnite case A= (a, a + 1, a + 22, . . . , a +k2) presents signiﬁcant challenges. The corre-

sponding optimization problem OB(M) is diﬃcult to solve. We establish several bounds using

the Four-Square Theorem, establish certain stable properties by using generating functions,

and ﬁnally prove the conjecture about g(A).

The paper is structured as follows. In Sections 2 and 3, we investigate the Frobenius

number of two distinct inﬁnite sequences, speciﬁcally A′= (a, a + 12, a + 22, . . .) and A′=

(a, a + 1, a +p1, a +p2, . . .). For these sequences, the corresponding optimization problems

OB′(M) admit explicit solutions within the domain of Number Theory. This enables us to

ascertain the values of g(A′) for both sequences. In Section 4, we resolve the conjecture put

forth by Einstein et al. regarding g(a, a + 1, a + 22, . . . , a +k2). Section 5 concludes the paper

with a concluding remark.

2. Infinite Square Sequence Formula

The Frobenius formula for square sequences remains an open problem.

Open problem 2.1 ([5]).Let A= (a, a + 1, a + 4, . . . , a +k2), where k∈Pand a > 2. How

can we characterize g(A)?

ON FROBENIUS FORMULAS OF POWER SEQUENCES 3

Einstein et al. [5] conjectured that the Frobenius number for this sequence is given by

k2(a2+ca)−dfor some integers c, d, which depend on kand the residue class of amodulo

k2. Using a geometric algorithm, they demonstrated the validity of this formula for k=

(1,2,3,4,5,6,7) and corresponding a≥(1,1,16,24,41,67,136).

In this section, we begin by discussing a variation of this problem, which represents a

relatively simple case, before addressing the open problem in Section 4. We will primarily

focus on the Frobenius number g(A) for the case when kapproaches inﬁnity, i.e., when A=

(a, a + 12, a + 22, a + 32, . . .). It is true that larger values of kthat satisfy a+k2≥g(a, a + 1)

can be neglected, but including them simpliﬁes the analysis.

To calculate g(A), we need the following deﬁnition.

Deﬁnition 2.2. For any n∈P, we use the symbol ι(n)to denote

ι(n) = min{s|n=a2

1+a2

2+· · · +a2

s, ai∈P,1≤i≤s}.

That is, ι(n)is the minimum number of squares required to express nas a sum of squares.

The characterization of ι(n) is known in Number Theory, as we shall soon introduce.

Firstly, the Four-Square Theorem provides an upper bound for ι(n).

Lemma 2.3 (Lagrange theorem [6]).Every positive integer is the sum of four squares.

To determine the precise value of ι(n), additional results and notations are required. For

n∈P, the Standard Form of nis the unique factorization of ninto primes: n=pe1

1pe2

2· · · pek

where pi>1 are distinct primes, ei>0, for 1 ≤i≤k.

Lemma 2.4 ([6]).A number n∈Pis the sum of two squares if and only if, in the Standard

Form of n, all prime factors of the form 4m+ 3 (where m∈N) have even exponents.

Lemma 2.5 ([6]).A number n∈Pis the sum of three squares if and only if n̸= 4r(8t+ 7),

where r, t ∈N.

With these lemmas in place, we can now determine ι(n) as follows.

Theorem 2.6. For any n∈P, if the Standard Form of nis n=pe1

1pe2

2· · · pek

k, then nfalls

into one of the following four categories:

1) For every 1≤i≤k,eiis even, indicating that nis a perfect square.

2) There exists a 1≤j≤ksuch that ejis odd, and for all 1≤i≤kwith pi≡3 mod 4,

eiis even.

3) nis of the form 4r(8t+ 7), where r, t ∈N.

4) Otherwise.

Accordingly, we have:

ι(n) = 









1if n∈type1)

2if n∈type2)

4if n∈type3)

3if n∈type4)

4 FEIHU LIU1AND GUOCE XIN2,∗

Proof. The proof of this theorem is straightforward, as it follows directly from Lemmas 2.3,

2.4, and 2.5. □

To characterize g(A), we need the following lemma.

Lemma 2.7. Let A= (a, a + 12, a + 22, a + 32, . . .). For 1≤r≤a−1, we have

Nr= min{ι(ma +r)·a+ma +r|m∈N}.

Proof. We appropriately generalize the deﬁnition of Nr. We have

Nr= min (∞

i=1

xi(a+i2)|

∞

i=1

xi(a+i2)≡rmod a, xi∈N, i ≥1)

= min ( ∞

i=1

xi!·a+ma +r|

∞

i=1

xi·i2=ma +r, m, xi∈N, i ≥1)

= min{ι(ma +r)·a+ma +r|m∈N}.

(Note: there are only a ﬁnite number of xithat are not 0.) □

Theorem 2.8. Let A= (a, a + 12, a + 22, a + 32, . . .). For 1≤r≤a−1, if there exists an r

such that ι(r) = 4, ι(a+r)≥3, ι(2a+r)≥2, then

g(A)=3a+ max{r|ι(r) = 4, ι(a+r)≥3, ι(2a+r)≥2}.

Proof. By Lemma 2.7 and the deﬁnition g(A) = max{Nr} − a, this result follows trivially. □

If the above theorem does not apply, then we have the following result.

Theorem 2.9. Let A= (a, a + 12, a + 22, a + 32, . . .). For 1≤r≤a−1, if the condition in

Theorem 2.8 is not satisﬁed and at least one of the following three conditions is met:

1) There exists an rsuch that ι(r) = 4 and ι(a+r) = 2;

2) There exists an rsuch that ι(r) = 4,ι(a+r)≥3, and ι(2a+r) = 1;

3) There exists an rsuch that ι(r) = 3 and ι(a+r)≥2.

Then

g(A)=2a+ max{r|the r in conditions 1), 2), or 3)}.

In order to gain a clearer understanding of the above theorem, we provide Table 1 in the

appendix.

Conjecture 2.10. Let A= (a, a + 12, a + 22, a + 32,...,). If a > 30, then Theorem 2.8 always

applies to give

g(A) = 3a+ max{r|ι(r) = 4, ι(a+r)≥3, ι(2a+r)≥2}.

By examining Tables 1 in the appendix, we intuitively ﬁnd that Conjecture 2.10 is likely

to be correct. Theorem 2.9 appears to be valid only for a= 4,5,7,9,10,11,13,19,21,22,30. On

the other hand, the ﬁrst numbers in the sequence 4r(8t+7) for (r, t ∈N) are 7,15,23,28,31,39,47, . . ..

To refute Conjecture 2.10, we would need to ﬁnd a number a > 30 such that ι(a+4r(8t+7)) ≤2

or ι(2a+ 4r(8t+ 7)) = 1 holds for any 4r(8t+ 7) < a. We guess that it is impossible.

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

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

10 玖币 0人已下载

立即下载

摘要：

ONFROBENIUSFORMULASOFPOWERSEQUENCESFEIHULIU1ANDGUOCEXIN2,∗Abstract.LetA=(a1,a2,...,an)beasequenceofrelativeprimeintegers,eachgreaterthanorequalto2.TheFrobeniusnumberg(A)representsthelargestintegerthatcannotbeexpressedasanonnegativelinearcombinationoftheelementsinA.Ourrecentworkhasintroducedacombinat...

展开>> 收起<<

ON FROBENIUS FORMULAS OF POWER SEQUENCES FEIHU LIU1AND GUOCE XIN2 Abstract. LetA a1 a2 . . . a n be a sequence of relative prime integers each greater.pdf

共16页,预览4页

还剩页未读，继续阅读

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

ON FROBENIUS FORMULAS OF POWER SEQUENCES FEIHU LIU1AND GUOCE XIN2 Abstract. LetA a1 a2 . . . a n be a sequence of relative prime integers each greater

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: