Axioms for a theory of signature bases

2025-05-02 0 0 1.07MB 36 页 10玖币

侵权投诉

Pierre Lairez #

Université Paris-Saclay, Inria, 91120 Palaiseau, France

Abstract Twenty years after the discovery of the F5 algorithm, Gröbner bases with signatures are still

challenging to understand and to adapt to dierent settings. This contrasts with Buchberger’s algorithm,

which we can bend in many directions keeping correctness and termination obvious. I propose an

axiomatic approach to Gröbner bases with signatures with the purpose of uncoupling the theory and the

algorithms, giving general results applicable in many dierent settings (e.g. Gröbner for submodules,

F4-style reduction, noncommutative rings, non-Noetherian settings, etc.), and extending the reach of

signature algorithms.

2012 ACM Subject Classiﬁcation Computing methodologies →Algebraic algorithms

Keywords and phrases Gröbner basis, F5 algorithm, signature basis

Funding This work has been supported by the European Research Council under the European Union’s

Horizon Europe research and innovation programme, grant agreement 101040794 (10000 DIGITS); and

by the ANR grant ANR-19-CE40-0018 (De Rerum Natura).

1Introduction

Context Introduced by Faugère (2002) to compute Gröbner bases, the F5 algorithm proposes

the concept of signature to avoid the redundant computations that arise in Buchberger’s algo-

rithm (Buchberger, 1965, 1965/2006). Each polynomial handled by the algorithm is augmented

with a signature designed to enforce a fundamental postulate, which we may state as “two

elements with the same signature are substitutable”. We can ﬁnd precursive ideas in the work

of Gebauer and Möller (1986) and Möller et al. (1992) and signatures also share somes ideas

with Hilbert-driven algorithms (Traverso, 1996).

Today’s situation of signature algorithms is equivocal. F5’s relevance, from the pure aspect

of performance, was demonstrated by a success on cryptographic challenges early on (Faugère

& Joux, 2003). Moreover, the predictability of F5 in certain situations enables complexity

analyses that are particularly relevant in cryptanalysis (Bardet et al., 2015). But none of the

current best implementations for computing Gröbner bases uses signatures, be it Magma

(Bosma et al., 1997), msolve (Berthomieu et al., 2021), Singular (Decker et al., 2022) or Maple.

They prefer Buchberger’s algorithm, handling S-pairs as Gebauer and Möller (1988) do and

using simultaneous reductions in the F4 style (Faugère, 1999) – see the report of Monagan and

Pearce (2015) on this approach. The theoretical beneﬁts of signature algorithms are diminished

by a higher implementation complexity and a larger output (the signature bases computed

by signature algorithms are more constrained than Gröbner bases). More than benchmarks,

literature about signature algorithms is turned towards revealing the core ideas behind F5 and

understanding what makes a signature algorithm terminate. Termination is a very peculiar

aspect, not as transparent as termination of Buchberger’s algorithm. Nonetheless, thanks to

decisive work by Hashemi and Ars (2010), Gao et al. (2010), Arri and Perry (2011), Eder and

Perry (2011), and Gao et al. (2016) these goals have been reached in the polynomial case – see

the survey by Eder and Faugère (2017).

The point of studying signature algorithm may not be the quest of new world records for

arXiv:2210.13788v3 [cs.SC] 8 Jan 2024

2 Axioms for a theory of signature bases

polynomial system solving, but rather the understanding of signatures themselves, and what

we can extract from them. Signature bases convey extra information compared to Gröbner

bases, related to the syzygy module of the input generators. Many ideal-theoretic operations

– intersection, quotient, saturation, Ext modules – are related to syzygy modules (Stillman,

1990), and signature algorithms seem to give an ecient access to them (Gao et al., 2010;

Sun & Wang, 2011; Faugère, 2001; Eder et al., 2023). Porting these ideas to more general

settings is a strong motivation to engage in the study of signatures. Yet, in my view, the lack of

ﬂexibility of the theory of signature algorithms hinders further development, both practical

and theoretical. For example, modern implementations for computing Gröbner bases make it

clear that simultaneous reductions in the F4 style are key towards high performance. Yet, there

is no satisfactory description of a signature algorithm with F4-style reduction (Albrecht and

Perry (2010) do not prove termination and Eder and Faugère (2017, §13) are superﬁcial).

This work considers the setting of a module over an algebra over a ﬁeld, with well-ordered

monomials. This covers many interesting case but excludes some recent developments of

signature algorithms which demonstrate the wide applicability of the concept: signatures in

local rings (Lu et al., 2018), coecients in Euclidean rings (Eder et al., 2017), principal ideal

domains (Francis & Verron, 2020; Hofstadler & Verron, 2023), or Tate algebras (Caruso et al.,

2020), and signatures in a tropical setting (Vaccon & Yokoyama, 2017; Vaccon et al., 2018).

Contribution I propose a set of axioms that speciﬁes a context in which signature algorithms

are applicable. They ﬁt many known settings – such as solvable algebras (Sun et al., 2012) and

free algebras (Hofstadler & Verron, 2022) – and some previously unknown settings, such as

dierential algebras (§6.5). Very importantly, the axioms describe modules over a ring, rather

than focusing on the special case of ideals. While many ideal theoretic constructions (such as

ideal intersection) are best understood in terms of modules, they are not addressed in previous

works. The ideas of the most recent frameworks for signature algorithms (Eder & Perry, 2011;

Gao et al., 2016) work smoothly in this axiomatic setting, so many statements will of course be

familiar, yet with a wider applicability.

Working with axioms makes some useful ideas emerge. At least two of them are worth

attention. First, the concept of prebasis is introduced to precisely describe admissible inputs

for signature algorihms, or, in other words, to describe what it means for signatures to be

consistent. Previous works all starts by ﬁxing the input, crafting speciﬁc signatures, and devel-

oping the theory with respect to these speciﬁc signatures. This is overly restrictive. Moreover,

this approach does not highlight the essential properties of signatures, ensuring correctness

and termination, among the incidental properties of this speciﬁc construction. This is also

problematic when trying to deﬁne what signatures and signature bases are. Gröbner bases are

deﬁned by the equality

⟨lm 𝐺⟩=lm ⟨𝐺⟩

, or the conﬂuence of some rewriting system (e.g. Becker

& Weispfenning, 1993, Deﬁnition 5.37), we do not need to say a Gröbner basis of something. It

is a very desirable deﬁnition which should have an equivalent in the signature setting. The

main obstacle here is the deﬁnition of signatures, independently of the speciﬁc construction

that is usually performed for a given input. This raises an interesting question: given a set of

signatures – basically anything well-ordered on which act monomials – what are the admissible

inputs? Similarly, imagine running some signature basis algorithm from an input

𝑓1, . . . , 𝑓𝑚

, and

stopping it midway. In this intermediate state, we have polynomials

𝑔1, . . . , 𝑔𝑟

with signatures

deriving from the original input by legal operations on polynomials and signatures. These

signatures must be consistent in some sense. Can we characterize this consistency property

without refering to the original input? This leads to the concept of prebasis, that is a set of

P. Lairez 3

polynomials with signatures which satisfy the fundamental postulates of signatures (elements

with equal signatures are substitutable). I prove that if a set of sigpoly pairs is a Gröbner basis

in the module representation, then it is a prebasis (Theorem 24). A concrete application is

the reuse of signatures from one computation to another, which is a way to avoid redundant

computations.

Second, I introduce sigtrees to uncouple the termination criterion from the algorithms them-

selves. Sigtrees make a “one size ﬁts all” termination criterion. For Buchberger’s algorithm,

termination follows from a general principle, Dickson’s Lemma, not from ad hoc arguments. The

concept of sigtrees is a tentative to provide such a general argument. It proves the termination

of all known signature algorithms and also settles positively a conjecture in the classical poly-

nomial setting: the termination of signature algorithms with out-of-order signature handling

and the F5 reductant selection strategy (among all possible reductants, choose the most recent

one). We may blend in an F4-style reduction, the termination argument remains the same.

Lastly, as a didactic contribution, I try to emphasize an elemental feature of signature

bases (or rather, for that matter, rewrite bases), putting a clear distinction with Gröbner bases.

To check that a given set

𝐺

is a Gröbner basis of an ideal

𝐼

, it is enough to check that (1)

𝐺

generates

𝐼

, and (2) the S-pairs reduce to zero. Typically (1) will hold by design if

𝐺

has been

constructed from a generating set of

𝐼

by usual reduction steps. Checking (2) is more dicult

and requires arithmetic operations in the base ﬁeld. This is typically a costly operation. In

constrast, to check that a given set

𝐺

with signatures is a rewrite basis of an ideal

𝐼

, it is enough

to check that (1’)

𝐺

is a prebasis of

𝐼

, and (2’) the leading monomials and the signatures satisfy

some combinatorial property (Theorem 38). The concept of prebasis is introduced in Section 3.2,

but for the moment, it is enough to say that (1’) will hold by design if

𝐺

is obtained by allowed

reduction steps from an initial prebasis of

𝐼

. The important part is the nature of (2’): it requires

no arithmetic operations to be checked, only operations on monomials. Algorithms for signature

bases are all about exploiting this combinatorial structure. This reminds of staggered linear

bases introduced by Gebauer and Möller (1986) to compute Gröbner bases, they feature a

similar combinatorial structure – and the link with signatures have recently been investigated

by Hashemi and Javanbakht (2021).

Plan In Section 2, we deﬁne the algebraic structure in which we consider signature bases,

monomial modules, that are vector spaces with a “leading monomial” map and an action of

a monoid with some compatibility rules. We also introduce the rewriting system deﬁned by

the top reduction. In Section 3, we deﬁne signatures, signature bases, prebases, and rewrite

bases. We also state a combinatorial criterion for a set to be a rewrite basis. Section 4 gathers

secondary properties of rewrite bases, such as a precise comparison with signature bases, that

are not necessary for the next sections. Section 5 introduces Noetherian hypotheses, termi-

nation arguments and review algorithm templates. Section 6 illustrates the axioms by several

dierent settings in which they apply.

Acknowledgment I am grateful to Hadrien Brochet and Frédéric Chyzak for a very careful

reading and useful comments. I thank the referees for thoughtful reports.

2Gröbner bases

Before going to signatures, we lay down some deﬁnitions. The main ones are the deﬁnitions of

amonomial space – a vector space with a concept of leading monomial, see Section 2.2 – and

4 Axioms for a theory of signature bases

amonomial module – a monomial space endowed with a linear action of a (non necessarily

commutative) monoid, compatible with leading monomials, see Section 2.3.

In monomial spaces, we develop a (short) theory of top reduction modulo tail equivalence

(Section 2.2), using the terminology of rewriting systems (Section 2.1). Using rewriting systems

to describe the theory of Gröbner bases in polynomial rings is done in several textbooks (e.g.

Becker & Weispfenning, 1993; Winkler, 1996; Kreuzer & Robbiano, 2000; Mora, 2005): in a few

words, we say that a polynomial

𝑓

can be reduced by a polynomial

𝑔

, if we can cancel out one

of the terms of

𝑓

by substracting a scalar multiple of the leading monomial of

𝑔

. The context

of signatures puts the emphasis on top reduction – the reduction of the leading monomial –

as opposed to tail reduction. The practice of Gröbner bases computation also shows that tail

reduction steps are optional. They are irrelevant as far as termination and correctness is

concerned, to perform them or not is only a matter of performance. Lastly, tail reduction does

not enjoy nice properties. For example, if

𝑔

reduces

𝑓

then

𝑚𝑔

reduces

𝑚 𝑓

for any monomial

𝑚

in a polynomial setting. But this implication breaks if

𝑚

is a polynomial rather than a monomial,

or if

𝑓

and

𝑔

lie in a Weyl algebra, unless the reduction is a top reduction. All of these hints at

replacing tail reduction by a more ﬂexible tail equivalence and replace the customary reduction

by the top reduction modulo tail equivalence. This ﬁts the abstract setting of “reduction modulo

equivalence” developed by Huet (1980).

2.1 Rewriting systems

Let

𝑋

be a set and

→

a binary relation on

𝑋

. “

𝑥1

→𝑦

” reads “

𝑥

reduces to

𝑦

”. Following Huet

(1980), we deﬁne the following binary relations:1

𝑥𝑛

→𝑦, for 𝑛 > 0, if there is some 𝑧∈𝑋such that 𝑥1

→𝑧and 𝑧𝑛−1

→𝑦;

𝑥→𝑦if 𝑥=𝑦or 𝑥𝑛

→𝑦for some 𝑛 > 0, this is the reﬂexive transitive closure of 1

→;

𝑥↑𝑦if there is some 𝑧∈𝑋such that 𝑧→𝑥and 𝑧→𝑦;

𝑥↓𝑦if there is some 𝑧∈𝑋such that 𝑥→𝑧and 𝑦→𝑧.

The relation

→

is Noetherian if there is no inﬁnite sequence

𝑥01

→𝑥11

→ · · ·

. An element

𝑥∈

𝑋is 1

→-reduced if there is no 𝑦∈𝑋such that 𝑥1

→𝑦. If 𝑥→𝑦and 𝑦is 1

→-reduced, then 𝑦is a

normal form of

𝑥

. If

→

is Noetherian, then every element has at least one normal form. The

relation

→

is conﬂuent if

𝑥↑𝑦

implies

𝑥↓𝑦

for any

𝑥, 𝑦 ∈𝑋

. If

→

is conﬂuent, then any

𝑥∈𝑋

has at most one normal form.

Moreover, given an equivalence relation ⌣on 𝑋, we deﬁne:

𝑥˘

↑𝑦if there are 𝑧, 𝑧′∈𝑋such that 𝑧 ⌣ 𝑧′,𝑧→𝑥and 𝑧′→𝑦;

𝑥˘

↓𝑦if there are 𝑧, 𝑧′∈𝑋such that 𝑧 ⌣ 𝑧′,𝑥→𝑧and 𝑦→𝑧′;

The relation 1

→is conﬂuent modulo ⌣if 𝑥˘

↑𝑦implies 𝑥˘

↓𝑦, for any 𝑥, 𝑦 ∈𝑋.

2.2 Top reduction

▶

Deﬁnition 1 (Monomial space, leading monomial,

≡lt

).Amonomial space over a ﬁeld

𝐾

-linear space

𝑀

with a basis

𝐵⊂𝑀

endowed with a well-order relation

⩽

. The leading

monomial of

𝑓∈𝑀

, denoted

lm 𝑓

, is the

⩽

-maximal element of

𝐵

with a nonzero coecient in

𝑓

Actually Huet denotes either

→

the one-step reduction, which I denote only

→

, and

∗

→

the multistep

reduction, which I denote →.

P. Lairez 5

or 0if

𝑓=

0. The set of leading monomials of

𝑀

is deﬁned to be the well-ordered set

𝐵∪{0}

where 0is added as the smallest element.

An equivalence relation

≡lt

is deﬁned on

𝑀

𝑥≡lt 𝑦

𝑥=𝑦=

0or

lm(𝑥−𝑦)<lm 𝑥

, to be

understood as “𝑥and 𝑦have the same leading term”.

The convention that

0is useful to simplify many statements: being able to write

lm 𝑓

without checking that

𝑓≠

0avoids a case distinction. From now on, we ﬁx a ﬁeld

𝐾

and a

monomial space 𝑀over 𝐾. The set of leading monomials of 𝑀is denoted M.

▶

Remark 2 (Equivalent monomial spaces). Dierent choices of a basis

𝐵

may lead to equivalent

monomial spaces, in the following sense. Another well-ordered basis

𝐵′

𝑀

gives an equivalent

monomial space if there is an increasing bijection

𝜄

𝐵→𝐵′

such that

lm′𝑓=𝜄(lm 𝑓)

where

lm′𝑓

is the leading monomial of

𝑓

relatively to

𝐵′

. The theory is described only using

not the basis

𝐵

, so it does not distinguish between equivalent monomial spaces. From an

axiomatic point of view, we can check that the maps

from

𝑀

onto a well ordered set that

come from a well-ordered basis, are exactly the maps satisfying

L1 ∀𝑥∈𝑀, lm 𝑥=0⇔𝑥=0;

L2 ∀𝑥, 𝑦 ∈𝑀, lm 𝑥=lm 𝑦≠0⇔ ∃𝜆∈𝐾×,lm(𝑥−𝜆 𝑦)<lm 𝑥.

For a given

𝑓∈𝑀

, we do not deﬁne the terms of

𝑓

, its monomial support, or the coecient of a

monomial in

𝑓

, because these notions depend on a speciﬁc choice of

𝐵

, which indicates that

they are irrelevant in our setting.

▶

Example 3. For polynomial rings, the monomial basis is a very natural choice. In a noncom-

mutative setting however, there may be several natural bases. For example, the Weyl algebra

𝑊1

generated by two elements

𝑥

and

𝜕

subject to the relation

𝜕𝑥 =𝑥𝜕 +

1, the two natural bases

are

𝐵={𝑥𝑛𝜕𝑚}

and

𝐵′={𝜕𝑚𝑥𝑛}

(with the same possible orderings as the polynomial case).

These two bases give equivalent monomial spaces.

▶Deﬁnition 4 (Top reduction, →𝐸).For any 𝐸⊆𝑀, the top reduction 1

→𝐸is deﬁned on 𝑀by

𝑥1

→𝐸𝑦⇔lm 𝑦 < lm 𝑥and ∃𝜆∈𝐾×,∃𝑒∈𝐸, 𝑦 =𝑥−𝜆𝑒.

In other words,

𝑥1

→𝐸𝑦

𝑦

is the result of cancelling the leading monomial of

𝑥

using a

reducer in

𝐸

. In this situation, we always have

𝜆𝑒 ≡lt 𝑥

. Since

𝑥1

→𝐸𝑦

implies

lm 𝑥 < lm 𝑦

, and

the set of leading monomials is well-ordered, it is clear that 1

→𝐸is Noetherian.

▶

Deﬁnition 5 (Tail equivalence,

⌣𝐸

↑𝐸

↓𝐸

).For any subset

𝐸⊆𝑀

, we deﬁne a relation

⌣𝐸

on 𝑀, called tail equivalence, deﬁned by

𝑥1

⌣𝐸𝑦⇔ ∃𝜆∈𝐾×,∃𝑒∈𝐸, 𝑦 =𝑥−𝜆𝑒 and lm 𝑒 < lm 𝑥.

The reﬂexive transitive closure of

⌣𝐸

is denoted

⌣𝐸

. The conﬂuence relations

↑𝐸

and

↓𝐸

are

deﬁned using ⌣𝐸.

Note that

𝑥 ⌣𝐸𝑦

implies

𝑥≡lt 𝑦

. The tail equivalence is not a reduction since it is symmetric,

it is not deﬁned which side of an equivalence 𝑥 ⌣𝐸𝑦is more reduced.

The following statement is a variant, in the setting of monomials spaces, of Buchberger’s

well known criterion for polynomial ideals. For

𝐸⊆𝑀

, let

⟨𝐸⟩

denote the

𝐾

-linear subspace

generated by 𝐸.

▶

Theorem 6 (Buchberger’s criterion for monomial spaces).Let

𝐸

be a subset of

𝑀

. The following

assertions are equivalent:

(Characterization by leading monomials)

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

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

10 玖币 0人已下载

立即下载

摘要：

AxiomsforatheoryofsignaturebasesPierreLairez#UniversitéParis-Saclay,Inria,91120Palaiseau,FranceAbstractTwentyyearsafterthediscoveryoftheF5algorithm,Gröbnerbaseswithsignaturesarestillchallengingtounderstandandtoadapttodifferentsettings.ThiscontrastswithBuchberger’salgorithm,whichwecanbendinmanydirec...

展开>> 收起<<

Axioms for a theory of signature bases.pdf

共36页,预览5页

还剩页未读，继续阅读

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

Axioms for a theory of signature bases

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: