Eugenio Marinelli
email: eugenio.marinelli@eurecom.fr

Omer Sella
email: osella@imperial.ac.uk

Thomas Heinis
email: t.heinis@imperial.ac.uk

Eddy Ghabach
email: eddy.ghabach@eurecom.fr

Thomas Bolbroe
email: thomasbolbroetbo@sa.dk

Digital Preservation with Synthetic DNA

Keywords: DNA storage, long-term archival, preservation, SIARD-DK

The growing adoption of AI and data analytics in various sectors has resulted in digital preservation emerging as a cross-sectoral problem that affects everyone from data-driven enterprises to memory institutions alike. As all contemporary storage media suffer from fundamental density and durability limitations, researchers have started investigating new media that can offer high-density, longterm preservation of digital data. In the European Union-funded Future and Emerging Technologies project OligoArchive, we are exploring one such media, namely, synthetic Deoxyribo Nucleic Acid (DNA). In this paper, we provide an overview of the ongoing collaboration between project OligoArchive and the Danish National Archive in preserving culturally important digital data with synthetic DNA.

INTRODUCTION

Today, we live in an increasingly digital society. Digital data pervades all disciplines and has established itself as the bed rock that drives our society, from enabling data-driven decisions based on machine learning, to encoding our collective knowledge compactly in a collection of bits. Thus, preservation of digital data has emerged as an important problem that must be addressed by not just memory institutions today, but also by institutions in several other sectors.

In order to preserve digital data, it is necessary to first store the data safely over a long time frame. Historically, this task has been complicated due to several issues associated with digital storage Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. BDA '21, October 25-28, 2021, Paris, France © 2021 Association for Computing Machinery. ACM ISBN 978-x-xxxx-xxxx-x/YY/MM. . . $15.00 https://doi.org/10.1145/nnnnnnn.nnnnnnn media. All current media technologies suffer from density scaling limitations resulting in storage capacity improving at a much slower rate than the rate of data growth. For instance, Hard Disk Drive (HDD) and magnetic tape capacity is improving only 16-33% annually, which is much lower than the 60% growth rate of data [START_REF] Fontana | Mooreâs law realities for recording systems and memory storage components: HDD, tape, NAND, and optical[END_REF]. All current media also suffer from media decay that can cause data loss due to silent data corruption, and have very limited lifetime compared to the requirements of digital preservation. For instance, HDD and tape have a lifetime of 5-20 years. A recent survey by the Storage and Networking Industry Association stated that several enterprises regularly archive data for much longer time frames [START_REF]100 Year Archive Requirements Survey 10 Years Later[END_REF]. Thus, the current solution for preserving data involves constantly migrating data every few years to deal with device failures and technology upgrades. A recent article summarized the financial impact of such media obsolescence on the movie industry [START_REF] Perlmutter | The Lost Picture Show[END_REF].

In project OligoArchive [START_REF] Appuswamy | OligoArchive: Using DNA in the DBMS storage hierarchy[END_REF], we are exploring a radically new storage media that has received a lot of attention recently-Deoxyribo Nucleic Acid (DNA) [START_REF] Church | Next-Generation Digital Information Storage in DNA[END_REF][START_REF] Erlich | DNA Fountain enables a robust and efficient storage architecture[END_REF][START_REF] Goldman | Toward Practical High-capacity Low-maintenance Storage of Digital Information in Synthesised DNA[END_REF][START_REF] Organick | Random access in large-scale DNA data storage[END_REF]. DNA is a macro-molecule that is composed of smaller molecules called nucleotides. There are four types of nucleotides: Adenine (A), Cytosine (C), Guanine (G), and Thymine (T). DNA used for data storage is typically a single-stranded sequence of these nucleotides, also referred to as an oligonucleotide (oligo). DNA possesses several key advantages over current storage media. First, it is an extremely dense three-dimensional storage medium with a capacity of storing 1 Exabyte/𝑚𝑚 3 which is eight orders of magnitude higher than magnetic tape, the densest medium available today [START_REF]Semiconductor Synthetic Biology Roadmap[END_REF]. Second, DNA is very durable and can last millennia in a cold, dry, dark environment. A recent project that attempted to resurrect the Woolly Mammoth using DNA extracted from permafrost fossils that are 5000 years old is testament to the durability of DNA even under adverse conditions [START_REF] Shapiro | Mammoth 2.0: will genome engineering resurrect extinct species?[END_REF]. Thus, data once stored in DNA can be left untouched without repeated migration to deal with technology upgrades. Third, as long as there is life on earth, we will always have the necessity and ability to sequence and read genomes, be it for assembling the genome of a previously-unknown species, or for sequencing the genome to detect diseases causing variations. As a result, unlike contemporary storage technologies, where the media that stores data and the technology to read data are tightly interlinked, DNA decouples media (biological molecules) from read technology (sequencing), thus reducing media obsolescence issues.

In this work, we provide an overview of the ongoing collaboration between the Danish National Archive and project OligoArchive in demonstrating a holistic solution for long-term preservation of culturally significant data using DNA. We present a motivating use case for long-term digital preservation, outline the challenges involved in using DNA as a digital storage medium, and present the end-to-end pipeline we have put in place to overcome these challenges.

CONTEXT AND BACKGROUND 2.1 Danish National Archive Use Case

The Danish National Archives is a knowledge center documenting the historical development of the Danish society. The archive collects, preserves and provide access to original data with the purpose of supporting current and future possible needs of the Danish community -public authorities as well as private citizens. A huge part of this work includes the preservation of digitally created and retro-digitized data securely and cost-effectively. Thus, the archive has received and preserved such data since the 1970s.

The archival material used for this work consists of selected hand-drawings made by the Danish king Christian IV (1577-1648). Although his reign was marked by military defeat and economic decline, Christian IV stands out as one of the most prominent, popular and admired characters in the line of Danish kings. The hand-drawings date to the period 1583-1591 where the king was 6-14 years old. The material is a part of a larger archival unit consisting of numerous documents and records1 . The specific image2 used for this experiment presents a naval battle between several warships. Besides emphasizing the young king's admiration for warfare and naval tactics, the material further indicates his high level of cultural education as well as his talent for drawing. At Danish National Archive, the material is thus ranked as having "Enestående National Betydning" (meaning unique national significance).

DNA storage challenges

Using DNA as a digital storage medium requires mapping digital data from its binary form into a sequence of nucleotides using an encoding algorithm. Once encoded, the nucleotide sequence is used to synthesize DNA using a chemical process that assembles the DNA one nucleotide at a time. Data stored in DNA is read back by sequencing the DNA molecules and decoding the information back to the original digital data.

A simple way to convert bits into nucleotides is to adopt a direct mapping that converts 2 bits into a nucleotide, for instance 00 to A, 01 to T, 10 to G, and 11 to C. This way a binary sequence is translated to an arbitrary sequence of nucleotides. However, such a simple approach is not feasible due to several biological limitations imposed by DNA synthesis and sequencing steps. First, DNA synthesis limits the size of an oligo between hundred to few thousands of nucleotides. Therefore, data must be divided into several pieces, with each piece being stored in an oligo. However, unlike current storage devices, oligos do not have logical addressing. Hence, index information that helps to identify the order in which the oligos, and hence the corresponding data bits, must be reassembled back during recovery must be stored together with the data bits and integrated in each oligo.

Second, oligos with repeat sequences (like ACACAC), or long consecutive repeats of the same nucleotide (like AAAAA), and oligos with extreme GC content, where the ratio of Gs and Cs in the oligo is less than 30% or more than 70%, are known to be difficult to synthesize, sequence, and process correctly. Thus, when constructing oligos, constraints need to be enforced to minimize homopolymer repeats and balance GC content. Further, care must be taken to minimize similarity across oligos as having too many oligos with similar nucleotide sequences can exacerbate sequencing errors and make it difficult to identify the original oligo.

Third, sequencing and synthesis are not error free even for wellformed oligos, as they introduce substitution errors, where a wrong nucleotide is reported, or indel errors, where spurious nucleotides are inserted or deleted. Both sequencing and synthesis also introduce bias. Some oligos are copied multiple times during synthesis, while others are not. Similarly, some oligos are read thousands of times during sequencing while others are not sequenced at all. Thus, it is important to use error correction codes in order to recover data back despite these errors.

In addition to the aforementioned media-level challenges in using DNA as a digital storage medium, there are also other problems associated with digital preservation that DNA does not solve. Any digital file stored on DNA is an encoded stream of bits whose interpretation makes sense only in the context of the application used to render, manipulate, and interact with that file format. While DNA might be able to store data for millennia, the associated applications and file formats might become obsolete. Thus, in addition to preserving data, it is also necessary to preserve the meaning of data by ensuring that data is stored in a preservation-friendly, non-proprietary format. Digital data can also be altered due to a variety of reasons and additional data-integrity techniques should be put in place to ensure that data retrieved from DNA can be trusted to be the same as the original source. The digital preservation community has long pioneered file formats, information systems, and operational methodologies for solving such format obsolescence issues [START_REF]Digital Preservation Handbook[END_REF]. Thus, a holistic DNA-based preservation solution should build on such techniques to solve both media and format obsolescence issues.

DESIGN

In this section, we will describe the end-to-end pipeline we have put in place to overcome the aforementioned challenges.

Overcoming format obsolescence with SIARD-DK

In Denmark, all public institutions and organizations that produce data worthy of persevering are legally bound to submit them to a public archive. As the vast majority of data in the Danish public sector are organized as databases with or without files in various formats, the focus has been on archiving these data in a standardized, system-independent and cost efficient manner. As a result, the archive has implemented a Danish version of the SIARD format (Software Independent Archiving of Relational Databases) [START_REF]SIARD (Software Independent Archiving of Relational Databases) Version 1[END_REF] named SIARD-DK for storing of such data. SIARD is an open format, designed for archiving relational databases in a vendor-neutral form and is used in the CEF building block "eArchiving". The first step in preserving data is extracting it and creating an SIARD-DK Archival information Package (AIP). In the creation of this particular AIP, the digitized material was converted to TIFF format. Information relevant to the images such as the preservation format of the files, their title, creator and original size, descriptive information, etc., was extracted and packaged together with relevant documentation in the AIP-format. This was done using proprietary tools developed at the Danish National Archive. The usage of SIARD for storing the files guarantee that the material is preserved in a rich format with relevant metadata stored in a standardized, system and vendor independent way. The resulting AIP is a single ZIP64 file that internally contains the TIFF images, in addition to XML and XSD files that store the schema of the archive and metadata information. This allows for strict validation of the AIP. Further, an MD5 value of each file is stored inside the archive and serves as the fixity to verify data integrity on retrieval.

Consensus Sequencing

Oligoarchive

DNA data storage pipeline

The end-to-end DNA media storage pipeline is presented in Figure 1. In the rest of this section, we will provide an overview of both the write path that takes as input the SIARD zip file and stores it in DNA, and the read path that restores back the zip file from DNA.

Write Path.

In order to store the archive on synthetic DNA, the zip file is first encoded from binary into a quaternary sequence of oligonucleotides, and then synthesized to generate synthetic DNA. The steps for encoding the SIARD archive file into oligos is presented in Figure 2. During encoding, the file is read as a stream of bits and pseudo randomized. Randomization is applied to reduce the number of homopolymer repeats within oligos, and similarity across oligos when generating the oligos at a later stage. After randomization, error correction encoding is applied to protect the data against errors. We use large-block length Low-Density Parity Check (LDPC) codes [START_REF] Gallager | Low-density parity-check codes[END_REF] with a block size of 256,000 bits as the error correction code, as it has been shown to be able to recover data in the presence of intra-oligo errors, or even if entire oligos are missing [START_REF] Chandak | Improved read/write cost tradeoff in DNA-based data storage using LDPC codes[END_REF]. We configure LDPC to add 10% redundancy to convert each sequence of 256,000 bits into 281,600 bits with data and parity. Each 281,600 bit sequence is then used to generate a set of 300-bit sequences, where each 300-bits is composed of 281 data bits and a 19-bit index that is used to order the sequences. Each 300-bit sequence is then passed to a constrained code that converts it into an oligonucleotide sequence.

We provide a practical overview of the constrained code here, deferring rigorous mathematical definition to future work. The constrained code is essentially a finite state machine that views each oligo as a sequence of short symbols that are concatenated together. In our current configuration, the constrained code breaks up each 300-bit sequence into a series of ten 30-bit integers. Each 30-bit integer is fed as input to a deterministic finite state machine that takes as input the previous 16-nucleotide sequence, and a set of constraints (homopolymer repeat, GC ratio, etecetera) that each symbol must meet and produces a valid 16-nucleotide sequence corresponding to the 30-bits as output. Thus, each 300-bit sequence is encoded as concatenation of ten such symbols, each with a length of 16 nucleotides, leading to an oligo that is 160 nucleotides long. We would like to explicitly point out here that the length of an oligo is a configurable parameter. Thus, while we use 160 nucleotides in our current system due to favorable pricing provided by our synthesis provider, our encoder can generate shorter or longer oligos if necessary, and automatically adjust various aspects (like the 19-bit index and 281-bit data size) based on desired oligo length.

Read Path.

To retrieve back the SIARD archive, the DNA is sequenced in order to retrieve back the nucleotide sequence of oligos. As mentioned before, sequencing produces noisy copies of the original oligos that can contain insertion, deletion, or substitution errors, which are referred to as reads. In order to infer the original oligos from the reads, we use a consensus procedure. Concretely, we structure this process as sequence of three algorithms, as depicted in Figure 3. First, we identify all pairs of strings that are similar to each other. As modern sequencers produce hundreds of millions of reads, this first task is an extremely computationally intensive due to use of edit distance as a metric for comparing strings. Thus, we have developed an efficient similarity join algorithm, called OneJoin [START_REF] Marinelli | OneJoin: Cross-architecture, scalable edit similarity join for DNA data storage using oneAPI[END_REF], that exploits the fact that due to randomization during encoding, reads corresponding to the same original oligo are "close" to each other despite some errors and "far" from the reads related to other oligos. The results obtained from the join algorithm are then used to quickly identify clusters of strings that are similar to each other. Each cluster thus groups all reads belonging the same oligo. Finally, we apply a position-wise consensus procedure that uses multiple reads to infer the original oligo in each cluster using a sequence alignment procedure [START_REF] Yan | Accel-align: A fast sequence mapper and aligner based on the seed-embed-extend method[END_REF]. We would like to point out here that not all oligos need to be correctly inferred. In fact, as we show later, some original oligos might not appear at all in the inferred set, and other inferred oligos might have errors. We rely on the parity added by LDPC codes at a higher level to recover data despite these errors.

The inferred oligos are then passed to the decoder which reverses the steps shown in Figure 2. The constrained code is first used to convert each 160nt oligo back into 300 bit sequences. The index stored in each 300 bits is used to reassemble bits back in the correct order. The LDPC decoder is then used to recover back data even if some bits were wrongly decoded, or some bits were zeroed out as corresponding oligos were missing. The decoded data is then derandomized to obtain a stream of bits that corresponds to the SIARD zip file.

EVALUATION

At this stage of our collaboration, we have assembled the entire pipeline. We are in the process of carrying out a real-life, large-scale synthesis and simulation experiments. As we do not have results from real experiments yet, we will provide a preliminary, simulationdriven evaluation in this section. Note that we simulate only the synthesis and sequencing steps in Figure 1. We encode/decode the real dataset using our pipeline.

The raw SIARD archive that is fed as input to our pipeline is 12.9MB in size. With redundancy added by LDPC, the resulting binary data to be stored on DNA is 14.19MB in size. We encode the SIARD archive generating 404,863 oligos, each with a length of 160 nucleotides. This corresponds to a density of 1.837 bits-pernucleotide. Using these original oligos, we then generate five million reads by using a short-read simulator3 tool, that adds random errors such as insertion, substitution, and deletion in each read to mimic the actions of an Illumina DNA sequencer. This corresponds to an average coverage of 11×, meaning that each oligo, on average is covered by 11 noisy copies. Note that, while the average coverage is 11×, the overall coverage typically follows a negative binomial distribution, with some oligos being covered hundreds of times, and some being not covered at all. Using the consensus procedure described earlier, we obtain the inferred oligos using this simulated dataset. We then use the constrained code to convert these inferred oligos into 300-bit sequences, and reassemble them in order based on the 19-bit index. At this stage, we can have a situation where an oligo is missing due to sequencing simulation bias, or an oligo could not be converted back into 300-bits by the deterministic finite state machine due to errors. In both cases, there will be a corresponding index whose data bits cannot be recovered. We insert a sequence of zero bits for such indices and rely on the redundancy added by LDPC to recover back the missing data.

Table 1 shows statistics for the rebuilding process of SIARD archive. The figures are obtained by comparing the inferred oligo for a certain index with the corresponding true oligo. We see that we are able to infer 404,727 oligos that correspond to 99.97% of the original oligos perfectly without errors. In addition 128 oligos were inferred with some errors, and 9 oligos were completely missing. Note that errors in an oligo does not imply that the entire oligo is different from the original one as they typically differ only in few nucleotides. For this reason, we also report the difference between inferred data and original in terms of number of bits. Despite these errors, our decoder was able to recover back the original archive completely due to error correction provided by the LDPC code.

#Original

CONCLUSION AND FUTURE WORK

In this work, we provided an overview of the ongoing collaboration between project OligoArchive and the Danish National Archive in using DNA to preserve culturally significant digital data. Building on prior work on molecular information storage and digital preservation, we presented a holistic, end-to-end pipeline for preserving both data and the meaning of data on DNA, and tested the pipeline using simulation studies. There are several avenues of future work we are pursuing. First, as described earlier, we are in the process of carrying out a large-scale experiment to validate our pipeline using real data. Second, we are investigating various optimizations to both encoding and consensus algorithms to support alternate synthesis and sequencing technologies with potentially higher error rates. Finally, while we addressed the question of preserving data in this work, we left open the question of preserving the decoding algorithm itself. Recent work has investigated the design of nested universal emulators that can be used to preserve and emulate such decoders using analog media like film or archival paper [START_REF] Appuswamy | Universal Layout Emulation for Long-Term Database Archival[END_REF]. Thus, we are investigating methods to combine DNA-based digital data storage with analog media-based decoding logic storage.

Figure 2 :

 2 Figure 1: DNA Storage Pipeline

Figure 3 :

 3 Figure 3: Various steps in the consensus procedure.

Table 1 :

 1 Statistics for decoding of SIARD archive

	Oligos	404863
	#Correctly Inferred Oligos 404726
	#Incorrectly Inferred Oligos	128
	#Missing Oligos	9
	#Incorrect bits	8640

https://www.flickr.com/photos/statensarkiver

https://www.flickr.com/photos/statensarkiver/28273082238

https://sourceforge.net/projects/bbmap/

ACKNOWLEDGMENTS

This work was partially funded by the European Union's Horizon 2020 research and innovation programme, project OligoArchive (grant agreement No 863320).


S D Adhikari

L Boza
email: boza@us.es

Shalom Eliahou
email: eliahou@univ-littoral.fr

M P Revuelta

M I Sanz
email: isanz@us.es

Departamento De

Univ Littoral

C Ôte D'opale

E A 2597 -Lmpa -Laboratoire

Departamento De Matem

Numerical semigroups of Szemerédi type

Keywords: 2010 Mathematics Subject Classification. 05C55, 11B25, 11D07, 20M13 Arithmetic progression, van der Waerden number, multiplicity, Frobenius number, conductor

published or not. The documents may come   L'archive ouverte pluridisciplinaire

A famous theorem of Szemerédi states that any subset of N + of positive upper density contains arbitrary long arithmetic progressions. Informally, an equivalent finitary version states that given any length k ≥ 3, any sufficiently dense subset of a sufficiently large integer interval contains an arithmetic progression of length k.

Our purpose in this paper is to introduce and study a closely related set Sz(k, δ), parametrized by a desired length k ≥ 3 and density 0 < δ ≤ 1. That set, introduced in Section 2, consists of all positive integers n satisfying Szemerédi's theorem relative to k and δ. In Section 3, we prove that Sz(k, δ) ∪ {0} is a numerical semigroup. Section 4 displays value tables of closely related functions r 3 (n), r 4 (n). In the last Section 5, we completely determine Sz(k, δ) for (k, δ) = (4, 1/2) and for more than thirty pairs (3, δ) with δ > 1/5. Interestingly, in a majority of these examples, it occurs that Sz(k, δ) contains some integer n but not n + 1. Said otherwise, the conductor of the numerical semigroup Sz(k, δ) ∪ {0} does not necessarily coincide with its multiplicity. The simplest occurrence of this phenomenon is the case Sz(3, 1/3), which contains 50 but not 51; more precisely, the corresponding multiplicity and conductor equal 49 and 55, respectively. That the set Sz(k, δ) is not empty follows from a famous theorem of Szemerédi, stated here in its finitary version [START_REF] Szemerédi | On sets of integers containing no k elements in arithmetic progression[END_REF]. Theorem 2.2 (Szemerédi). Given any integer k ≥ 3 and real number 0 < δ ≤ 1, there exists n(k, δ) ∈ N + such that for any integer n ≥ n(k, δ), every subset A ⊆ [1, n] of density |A|/n ≥ δ contains an arithmetic progression of length k.

We shall denote M(k, δ) = min Sz(k, δ). Observe that M(k, δ) owes its existence to Szemerédi's theorem above as already noted, and that 1

if δ ≤ (k -1)/k, then M(k, δ) ≥ k + 1 since no proper subset of [1, k] contains an arithmetic progression of length k. As for δ = 1, it is clear that Sz(k, 1) = [k, ∞[ for all k ∈ N + .
2.1. The function r k (n). Closely linked to Szemerédi's theorem is the function r k (n), defined as the maximal cardinality of a subset A ⊆ [1, n] containing no arithmetic progression of length k. Indeed, Szemerédi's theorem is equivalent to the asymptotic bound r k (n) = o(n). This function can be used to reformulate membership in Sz(k, δ), as follows.

Lemma 2.3. Let k ≥ 3 be an integer and let 0 < δ ≤ 1. Then, for every positive integer n, we have n ∈ Sz(k, δ) if and only if r k (n)/n < δ.

Proof. Assume n ∈ Sz(k, δ). Let A ⊆ [1, n] be a subset of cardinality r k (n) containing no arithmetic progression of length k. Then r k (n)/n = |A|/n < δ since n ∈ Sz(k, δ). Conversely, assume r k (n)/n < δ. Let A ⊆ [1, n] be a subset of density |A|/n ≥ δ. Then |A| ≥ nδ > r k (n).
Hence, by definition of r k (n), the subset A contains an arithmetic progression of length k. Therefore n ∈ Sz(k, δ).

2.2.

Comparison with the van der Waerden numbers. Not much explicit information about M(k, δ) seems to be currently available in the literature. For δ = 1/r with r ∈ N + , the number M(k, 1/r) is bounded below by the corresponding van der Waerden number W (k, r). Given integers k, r ≥ 2, recall that W (k, r) denotes the least integer M such that, for every r-coloring

of [1, M], there is a monochromatic arithmetic progression of length k in [1, M]. To show (1) M(k, 1/r) ≥ W (k, r),
let N = M(k, 1/r), and consider any r-coloring of [1, N]. Then some color class X ⊆ [1, N] is of density |X|/N ≥ 1/r, and hence X contains an arithmetic progression of length k which is monochromatic by construction. This settles (1), as desired.

The only exactly known van der Waerden numbers at the time of writing are given in the following table. See e.g. [START_REF]Van der Waerden numbers[END_REF], a web page which also displays lower bounds on W (k, r) for many more pairs (k, r).

W (3, 2) = 9 W (3, 3) = 27 W (3, 4) = 76 W (4, 2) = 35 W (4, 3) = 293 W (5, 2) = 178 W (6, 2) = 1132
In subsequent sections, we shall prove that Sz(k, δ) ∪ {0} is a numerical semigroup and shall determine it for several pairs (k, δ). We first recall some basic notions regarding numerical semigroups.

SZ(k, δ) ∪ {0} AS A NUMERICAL SEMIGROUP

A numerical semigroup is a cofinite submonoid of N. That is, a subset S ⊂ N containing 0, stable under addition and with finite complement N \ S. Equivalently, it is a subset of N of the form S = a 1 , . . . , a n = a 1 N + • • • + a n N for some globally coprime positive integers a 1 , . . . , a n .

Given a numerical semigroup S ⊆ N, the multiplicity of S is m = min(S \ {0}), its Frobenius number is F = max(Z \ S), that is its largest gap, and its conductor is c = F + 1 or, equivalently, the smallest integer c such that

[c, ∞[ ⊆ S. If S = a 1 , . . . , a n = a 1 N + • • • + a n N
with the a i increasing and globally coprime, the multiplicity of S is m = a 1 . But determining the Frobenius number of S from the sole generators a i is a notoriously difficult problem for n ≥ 3. See e.g. [START_REF] Curtis | On formulas for the Frobenius number of a numerical semigroup[END_REF][START_REF] Ramírez Alfonsín | Complexity of the Frobenius problem[END_REF]. As for n = 2, Sylvester proved long ago [START_REF] Sylvester | On subinvariants, i.e. semi-invariants to binary quantities of an unlimited order[END_REF] that the Frobenius number of a 1 , a 2 equals (a 1 -1)(a 2 -1) -1. See [START_REF] Ramírez Alfonsín | The Diophantine Frobenius problem[END_REF][START_REF] Rosales | Numerical semigroups[END_REF] for extensive information on numerical semigroups.

Our objective in this section is to prove that Sz(k, δ) ∪ {0} is a numerical semigroup, using only a weakened version of Szemerédi's theorem.

3.1. Stability under addition. Our first task is to prove that Sz(k, δ) is stable under addition. We shall need the following elementary lemma [START_REF] Adhikari | On the degree of regularity of a certain quadratic Diophantine equation[END_REF]. Lemma 3.1. Let A, E be nonempty finite sets such that A ⊆ E. Denote δ = |A|/|E| the density of A in E. Let E = E 1 • • • E r be a partition of E into r nonempty parts. Then there exists an index i ≤ r such that

|A ∩ E i |/|E i | ≥ δ. Proof. If |A ∩ E i |/|E i | < δ for all i, then ∑ i |A ∩ E i | < δ ∑ i |E i |. Since ∑ i |A ∩ E i | = |A| and ∑ i |E i | = |E|, this implies |A| < δ|E| = |A|, a contradiction.
Proposition 3.2. For any integer k ≥ 3 and 0 < δ ≤ 1, the set Sz(k, δ) ∪ {0} is stable under addition.

Proof. Let n 1 , n 2 ∈ Sz(k, δ). Let E = [1, n 1 + n 2 ]
, and consider the partition

E = E 1 E 2 with E 1 = [1, n 1 ] and E 2 = [n 1 + 1, n 1 + n 2 ]. Thus |E i | = n i for i = 1, 2. Let X ⊆ E be of density |X|/(n 1 + n 2 ) ≥ δ. We must show that X contains an arithmetic progression of length k. Let X i = X ∩ E i for i = 1, 2. By the above lemma, either |X 1 |/n 1 ≥ δ or |X 2 |/n 2 ≥ δ.
It follows that either X 1 or X 2 contains an arithmetic progression of length k, whence X also does. Thus n 1 + n 2 ∈ Sz(k, δ), as stated.

Cofiniteness in N.

It directly follows from Szemerédi's Theorem 2.2 that N \ Sz(k, δ) is finite since it implies that, for some n(k, δ) ∈ N + , every integer n ≥ n(k, δ) belongs to Sz(k, δ). However, that statement can also be deduced by elementary arguments from the following weaker version of Szemerédi's theorem. This version 'only' states that Sz(k, δ) is nonempty, and hence that the number M(k, δ) = min Sz(k, δ) exists, whereas the original version states that N \ Sz(k, δ) is finite. As shown here, these statements are equivalent. Indeed, below we shall only use the existence of M(k, 1/r) for k, r ∈ N + to deduce the cofiniteness of Sz(k, δ) in N in general. That is, we shall deduce Theorem 2.2 from its weaker version Theorem 3.3.

Let us start by observing that Sz(k, δ) is monotonous in the parameter δ.

Lemma 3.4. Let k ≥ 3 be an integer, and let

0 < δ 1 ≤ δ 2 ≤ 1. Then Sz(k, δ 1 ) ⊆ Sz(k, δ 2 ).
Proof. Let n ∈ Sz(k, δ 1 ). Every subset of [1, n] of density at least δ 2 has density at least δ 1 , whence contains an arithmetic sequence of length k.

Therefore n ∈ Sz(k, δ 2 ).

We shall first prove the cofiniteness of Sz(k, δ) when δ = 1/r with r ∈ N + , and shall then use the above lemma for δ arbitrary. The case δ = 1/r relies upon the following intermediary result. Proposition 3.5. Let k, r, n be integers with k ≥ 3 and r, n ≥ 2. If n ∈ Sz(k, 1/r) and n ≡ 1 mod r, then n -1 ∈ Sz(k, 1/r).

Proof. By Euclidean division by r with remainder in [1, r], there are integers q,t such that n = qr + t with 1 ≤ t ≤ r. We have t ≥ 2 since n ≡ 1 mod r. Let X ⊆ [1, n -1] be any subset of density |X|/(n -1) ≥ 1/r. We claim that |X|/n ≥ 1/r. Indeed, we have r|X| ≥ n -1, whence |X| ≥ q + (t -1)/r. But since 2 ≤ t ≤ r, we have 1/r ≤ (t -1)/r < 1. Since |X| is an integer, it follows that |X| ≥ q + 1, whence r|X| ≥ qr + r ≥ qr + t = n, whence |X|/n ≥ 1/r. Thus X is still of density at least 1/r in [1, n]. It follows that X contains an arithmetic progression of length k. Therefore n-1 ∈ Sz(k, 1/r), as claimed.

Corollary 3.6. Let k, r be integers with k ≥ 3 and r ≥ 2. Then M(k, 1/r) ≡ 1 mod r.

Proof. Let n = M(k, 1/r) = min Sz(k, 1/r). Since n -1 /
∈ Sz(k, 1/r), the above proposition implies n ≡ 1 mod r, as desired. Proposition 3.7. For any integers k ≥ 3 and r ≥ 2, the complement N \ Sz(k, 1/r) is finite.

Proof. Set n = M(k, 1/r). Then n ≡ 1 mod r as seen above. Moreover, we have 2n ∈ Sz(k, 1/r), and 2n ≡ 2 mod r. It follows that 2n -1 also belongs to Sz(k, 1/r). Therefore Sz(k, 1/r) contains the numerical semigroup 2n -1, 2n , and in particular it contains all integers greater than or equal to the conductor of the latter semigroup, namely (2n -2)(2n -1) as given by the old result of Sylvester recalled above [START_REF] Sylvester | On subinvariants, i.e. semi-invariants to binary quantities of an unlimited order[END_REF].

3.3.

Completing the proof. We may now reach the objective of this section.

Theorem 3.8. For every integer k ≥ 3 and 0 < δ ≤ 1, the set Sz(k, δ) ∪ {0} is a numerical semigroup.

Proof. The stability of Sz(k, δ) under addition is given by Proposition 3.2. It remains to prove that its complement in N is finite, without invoking the full force of Theorem 2.2. There exists r ∈ N + such that 1/r ≤ δ. Since Sz(k, 1/r) ⊆ Sz(k, δ) by Lemma 3.4, and since the complement of Sz(k, 1/r) in N is finite by Proposition 3.7, the same holds for Sz(k, δ). We propose to call numerical semigroups of Szemerédi type those numerical semigroups S of the form S = Sz(k, δ) ∪ {0} for k ≥ 3 and 0 < δ ≤ 1.

3.4.

The number C(k, δ). Recall that M(k, δ) = min Sz(k, δ). Thus, in the standard terminology of numerical semigroups, the number M(k, δ) is the multiplicity of Sz(k, δ)∪{0}. We now introduce a notation for the conductor of that numerical semigroup.

Note that the conclusion of Corollary 3.12 may not necessarily hold for densities δ other than 1/r with r ≥ 2 an integer. For instance, with k = 3 and δ = 3/4, we have Sz(3, 3/4) = {3} ∪ [6, ∞[, so that M = 3 and C = 6, whence C > (M -1) 2 + 1.

EXACT VALUES OF r k (n)

Exact values of the functions r 3 (n) and r 4 (n) defined in Section 2.1 are currently known for n ≤ 187 and n ≤ 112, respectively. They are partly listed in the two tables below, which were read off from [START_REF] Gasarch | Finding large 3-free sets I: The small n case[END_REF] and [START_REF] Shao | On sets without k-term arithmetic progression[END_REF], respectively. In the next section, we shall use these values, in conjunction with Lemma 2.3, to determine Sz(k, δ) in many instances. We now determine Sz(3, δ) for various values of δ < 1, and Sz(4, 1/2), using Lemma 2.3 and the two tables above. In each case, we give the multiplicity M(k, δ), the conductor C(k, δ) and the full set Sz(k, δ).

n r 3 (n) n r 3 (n) n r 3 (n) n r 3 (n)
In most cases, the set Sz(3, δ) can be directly read off from the displayed values of r 3 (n) for n ≤ 187. Yet sometimes, we need upper bounds on r 3 (n)

  N = {0, 1, 2, . . . } and N + = N \ {0}. Given integers a ≤ b, we denote by [a, b] = {z ∈ Z | a ≤ z ≤ b} the integer interval they span, and [a, ∞[ = {z ∈ Z | z ≥ a}.

2 .Definition 2 . 1 .

 221 THE SET SZ(k, δ) Given any length k ≥ 3 and density 0 < δ ≤ 1, let Sz(k, δ) denote the set consisting of all n ∈ N + satisfying the following property: every subset X ⊆ [1, n] of density |X|/n ≥ δ contains an arithmetic progression of length k.

Theorem 3 . 3 .

 33 Given an integer k ≥ 3 and 0 < δ ≤ 1, there exists a positive integer n = n(k, δ) such that every subset A ⊆ [1, n] of density |A|/n ≥ δ contains an arithmetic progression of length k.

Thanks are due to Pierre Catoire, an undergraduate math student in Calais, for pointing out an error in a preliminary version of this statement.

Acknowledgments. The authors are grateful to the anonymous referees for their constructive and detailed suggestions on a preliminary version of this paper.

Notation 3.9. Let k ≥ 3 and 0 < δ ≤ 1. We shall denote C(k, δ) the conductor of the numerical semigroup Sz(k, δ) ∪ {0}.

We have [START_REF] Curtis | On formulas for the Frobenius number of a numerical semigroup[END_REF] M(k, δ) ≤ C(k, δ), since the multiplicity of any numerical semigroup is smaller than or equal to its conductor. Of course, M(k, 1) = C(k, 1) = k.

Here is yet another consequence of Proposition 3.5, similar in content and proof to Corollary 3.6.

Corollary 3.10. Let k, r be integers with k ≥ 3 and r ≥ 2. Then C(k, 1/r) ≡ 1 mod r.

Proof. The conductor n = C(k, 1/r) of Sz(k, 1/r) satisfies n-1 / ∈ Sz(k, 1/r). Hence n ≡ 1 mod r by Proposition 3.5.

We shall need the following characterization of the conductor. Proof. Denote S = Sz(k, 1/r). By Lemma 3.11, it suffices to show that S contains M consecutive integers starting from (M -1) 2 + 1, i.e. that

Recall from Proposition 3.5 that if n ∈ S and n ≡ 1 mod r, then n -

In particular, we have M ≡ 1 mod r by Corollary 3.6.

for any positive integer i ≥ 1. Then card(J i ) = i. We claim that J i ⊂ S for all i ≥ 1. Indeed, this holds for i = 1 since J 1 = {M}. For i ≥ 2 assume, by induction hypothesis, that the claim holds for i -1, i.e. that J i-1 ⊂ S.

for several n > 187. For that, we use the easy and well-known inequality (4)

for all k, n, i ≥ 1.

Determining the multiplicity M(k, δ) = min Sz(k, δ) is straightforward from Lemma 2.3 and the tables in Section 4. As for the conductor C(k, δ), it may be determined using Lemma 3.11. Tables 1 and2 below give Sz(k, δ) for more than 30 pairs (k, δ).


Frank Vega
email: vega.frank@gmail.com

The Smallest Gap Between Primes

Keywords: Twin prime conjecture, Prime numbers, Prime gap MSC Classification: 11A41, 11A25

A prime gap is the difference between two successive prime numbers. A twin prime is a prime that has a prime gap of two. The twin prime conjecture states that there are infinitely many twin primes. In May 2013, the popular Yitang Zhang's paper was accepted by the journal Annals of Mathematics where it was announced that for some integer N that is less than 70 million, there are infinitely many pairs of primes that differ by N. A few months later, James Maynard gave a different proof of Yitang Zhang's theorem and showed that there are infinitely many prime gaps with size of at most 600. A collaborative effort in the Polymath Project, led by Terence Tao, reduced to the lower bound 246 just using Zhang and Maynard results. In this note, using arithmetic operations, we prove that the twin prime conjecture is true.

Introduction

Leonhard Euler studied the following value of the Riemann zeta function (1734).

Proposition 1 It is known that [1, (1) pp. 1070]:

ζ(2) = ∞ k=1 p 2 k p 2 k -1 = π 2 6
, The Smallest Gap Between Primes Fig. 1 Roots of H 2 (x) [START_REF] Solver -Wolfram | C%2840%29X+%2B+ 2%5C%2841%29%5D+%2B+log%5C%2840%29Divide%5B%5C%2840% 29Power%5BX%2C2%5D+-+Power%5BX%2C%5C%2840%29Divide% 5B1%2C%5C%2840%29log%5C%2840%29X%5C%2841%29+%2B+1% 5C%2841%29%5D%5C%2841%29%5D%5C%2841%29%2CPower%5BX% 2C2%5D%5D%5C%2841%29%3D0[END_REF] Fig. 2 Roots of H 4 (x) [START_REF] Solver -Wolfram | C%2840%29X+%2B+ 4%5C%2841%29%5D+%2B+log%5C%2840%29Divide%5B%5C%2840% 29Power%5BX%2C2%5D+-+Power%5BX%2C%5C%2840%29Divide% 5B1%2C%5C%2840%29log%5C%2840%29X%5C%2841%29+%2B+1% 5C%2841%29%5D%5C%2841%29%5D%5C%2841%29%2CPower%5BX% 2C2%5D%5D%5C%2841%29%3D0[END_REF] where p k is the kth prime number (We also use the notation pn to denote the nth prime number).

Proposition 2 We know that if x ≥ 89693, there is at least one prime p in the interval x < p ≤ 1 + 1 log We use the following function:

Definition 1 For all x > 1 and a ≥ 0, we define the function:

Ha(x) = log( x x -1 ) - 1 x + a + log( x 2 - log(x)+1 √ x x 2
).

We state the following Propositions:

Proposition 3 For a sufficiently large positive value x, we have H 2 (x) < 0. Certainly, H 2 (x) is negative for all x ≥ 60000 since it is negative for x = 60000, strictly decreasing for x ≥ 60000 (because its derivative is lesser than 0 for x ≥ 60000) and its greatest root is between 50000 and 60000 (See Figure 1).

Proposition 4 For a sufficiently large positive value x, we have H 4 (x) > 0. Certainly, H 4 (x) is positive for all x ≥ 1.5 since it is positive for x = 1.5 and its unique root is between 1.4 and 1.5 (See Figure 2).

The following property is based on natural logarithms:

Proposition 5 [5, pp. 1]. For x > -1:

log(1 + x) ≤ x.
Putting all together yields the proof of the main theorem.

Theorem 1 The twin prime conjecture is true.

Infinite Sum

Lemma 1

∞ k=1 log( p k p k -1 ) -log(1 + 1 p k ) = log(ζ(2)).
Proof We obtain that

log(ζ(2)) = log( ∞ k=1 p 2 k p 2 k -1 ) = ∞ k=1 log( p 2 k (p 2 k -1) ) = ∞ k=1 log( p 2 k (p k -1) • (p k + 1) ) = ∞ k=1 log( p k p k -1 ) + log( p k p k + 1 ) = ∞ k=1 log( p k p k -1 ) -log( p k + 1 p k ) = ∞ k=1 log( p k p k -1 ) -log(1 + 1 p k ) by Proposition 1. □ 3 Partial Sum Lemma 2 p k ≤x log( p k p k -1 ) -log(1 + 1 p k ) = log( p k ≤x p 2 k p 2 k -1
).

Proof We obtain that log(

p k ≤x p 2 k p 2 k -1 ) = p k ≤x log( p 2 k (p 2 k -1) ) = p k ≤x log( p 2 k (p k -1) • (p k + 1) ) = p k ≤x log( p k p k -1 ) + log( p k p k + 1 ) = p k ≤x log( p k p k -1 ) -log( p k + 1 p k ) = p k ≤x log( p k p k -1 ) -log(1 + 1 p k ) by Proposition 1. □ 4 Main Insight Lemma 3 p k ≥pn p k p k -1 ) -log(1 + 1 p k ) = log( p k ≥pn p 2 k p 2 k -1
).

Proof We obtain that

p k ≥pn p k p k -1 ) -log(1 + 1 p k ) = ∞ k=1 log( p k p k -1 ) -log(1 + 1 p k ) - p k ≤pn-1 log( p k p k -1 ) -log(1 + 1 p k ) = log(ζ(2)) -log( p k ≤pn-1 p 2 k p 2 k -1 ) = log( p k ≥pn p 2 k p 2 k -1 )
by Lemmas 1 and 2. □

Proof of Theorem 1

Proof Suppose that the twin prime conjecture is false. Then, there would exist a sufficiently large prime number pn such that for all prime gaps starting from pn + 2, this implies that they are greater than or equal to 4. In addition, we assume that pn + 2 is also prime. We know that

H 2 (pn) + p k >pn H 4 (p k ) > H 2 (pn)
due to Proposition 4. That is equivalent to

p k ≥pn log( p k p k -1 ) - 1 p k+1 + p k ≥pn log( p 2 k - log(p k )+1 √ p k p 2 k ) > H 2 (pn) since -1 p k+1 ≥ -1 p k +4
and -1 pn+1 = -1 pn+2 under our assumption. Moreover, we obtain that

p k ≥pn log( p k p k -1 ) -log(1 + 1 p k+1 ) + p k ≥pn log( p 2 k - log(p k )+1 √ p k p 2 k ) > H 2 (pn) since -log(1 + 1 p k+1 ) ≥ -
p k ≥pn p 2 k p 2 k -1 ) + p k ≥pn log( p 2 k - log(p k )+1 √ p k p 2 k ) > H 2 (pn).
By Lemma 3, we know that log(

p k ≥pn p 2 k p 2 k -1 ) + p k ≥pn log( p 2 k - log(p k )+1 √ p k p 2 k ) = p k ≥pn 1 p k + 2 -log(1 + 1 p k ) + p k ≥pn H 2 (p k ) = p k ≥pn log( p k p k -1 ) -log(1 + 1 p k ) + p k ≥pn log( p 2 k - log(p k )+1 √ p k p 2 k ) = log( p k ≥pn p 2 k p 2 k -1 ) + p k ≥pn log( p 2 k - log(p k )+1 √ p k p 2 k ).
In this way, we have

log(1 + 1 pn ) + p k ≥pn 1 p k + 2 -log(1 + 1 p k ) + p k ≥pn H 2 (p k ) > H 2 (pn) which is 1 pn + 2 + p k >pn 1 p k + 2 -log(1 + 1 p k ) + p k >pn H 2 (p k ) > 0.
That is equivalent to

1 pn + 2 + p k >pn 1 p k + 2 -log(1 + 1 p k ) > 0.
Indeed, we know that -

p k >pn H 2 (p k ) > 0
by Proposition 3. However, we deduce that

p k >pn log(1 + 1 p k ) - 1 p k + 2 ≥ 1 pn + 2 where 1 pn + 2 = 1 p n+1 = ∞ k=1 1 2 k • (p n+1 ) which is k≥(n+1) log(1 + 1 p k ) - 1 p k + 2 - 1 2 k-n • p n+1 ≥ 0
since p n+1 = pn + 2 under our assumption. There exists always some k > (n + 1) such that

2 k-n • p n+1 ≫ 1 + 1 log 3 p n+1 m • p n+1 ≥ p n+m+1
for an arbitrary natural number m ≥ 1, where ≫ means "much greater than". For that reason,

k≥(n+1) log(1 + 1 p k ) - 1 p k + 2 - 1 2 k-n • p n+1 ≥ 0
is trivially satisfied by Proposition 2 when p n+1 ≥ 2996863034895 • 2 1290000 + 1 [START_REF] Caldwell | The Prime Database[END_REF]. Hence, the inequality

H 2 (pn) + p k >pn H 4 (p k ) > H 2 (pn)
would not hold by transitivity. For that reason, we obtain a contradiction under the supposition that the twin prime conjecture is false. By reductio ad absurdum, we prove that the twin prime conjecture is true. □

Conclusions

Until today, it has not been found a straightforward application to this problem. Of course, this is close related to prime numbers and prime numbers have been used for decades in the security of computer software including Artificial Intelligence solutions. However, the author used a computational and artificial intelligence as a tool for making his mathematical proof. This is a website called Wolfram Alpha and it has been developed by Wolfram Research for years. In this way, this proof reveals the capabilities and potential of such mathematical tool and it is an evidence of the promissory relation between pure and applied mathematics with the Artificial Intelligence.

  3 x • x [2, Proposition 5.4 pp. 242].


S D Adhikari

L Boza

S Eliahou

M P Revuelta

M I Sanz

On the degree of regularity of a certain quadratic Diophantine equation

Keywords: 2010 Mathematics Subject Classification. 05D10, 11B25, 11B30 Partition regularity, monochromatic solution, arithmetic progression, Szemerédi's theorem, Rado numbers, van der Waerden numbers

We show that, for every positive integer r, there exists an integer b = b(r) such that the 4-variable quadratic Diophantine equation (x 1y 1 )(x 2y 2 ) = b is r-regular. Our proof uses Szemerédi's theorem on arithmetic progressions.

Introduction

Denote N = {0, 1, 2, . . . } and N + = N\{0}. Given a polynomial f ∈ Z[x 1 , x 2 , . . . , x n ], let D( f ) denote the corresponding Diophantine equation

f (x 1 , x 2 , . . . , x n ) = 0.
This equation is said to be r-regular, for some integer r ≥ 1, if for every r-coloring of N + , there is a monochromatic solution to it. It is said to be regular if it is rregular for all r ≥ 1. The degree of regularity of D( f ), denoted dor(D( f )), is defined to be infinite if D( f ) is regular, or else, it is the largest r such that D( f ) is r-regular. Determining the degree of regularity of a given Diophantine equation is difficult in general, even if it is linear.

In this paper, we shall consider the 4-variable Diophantine quadratic equation

(x 1 -y 1 )(x 2 -y 2 ) = b, (1)
denoted Q(b), where b is a given positive integer. This equation is not regular. Indeed, it is not b-regular, and actually not even s-regular where s = √ b + 1, as witnessed by the s-coloring given by the class mod s; for if x 1 , y 1 , x 2 , y 2 are all congruent mod s, then (x 1y 1 )(x 2y 2 ) is divisible by s 2 , and hence cannot equal b since s 2 > b. That is, we have dor(Q(b)) ≤ √ b . Our purpose in this paper is to show that, nevertheless, the numbers dor(Q(b)) are unbounded as b varies.

Here is our main result.

Theorem 1.1. Given a positive integer r, there is a positive integer b = b(r) such that the equation (x 1y 1 )(x 2y 2 ) = b is r-regular.

A more specific version is stated and proved in Section 3. Our motivation to study this particular quadratic equation comes from previous work on the linear version

(x 1 -y 1 ) + (x 2 -y 2 ) = b,
and more generally on the 2k-variable linear Diophantine equation

(x 1 -y 1 ) + • • • + (x k -y k ) = b, (2)
the object of the following conjecture by Fox and Kleitman [START_REF] Fox | On Rado's Boundedness Conjecture[END_REF].

Conjecture 1.2. Let L k (b) denote equation (2). Then

max b∈N + dor(L k (b)) = 2k -1.
If true, that estimate would be best possible, since it is shown in [START_REF] Fox | On Rado's Boundedness Conjecture[END_REF] that dor(L k (b)) ≤ 2k -1 for all k, b ≥ 1. See [START_REF] Adhikari | On a conjecture of Fox and Kleitman on the degree of regularity of a certain linear equation[END_REF]2] for solutions of the Fox-Kleitman conjecture for k = 2 and 3, respectively, and [START_REF] Schoen | The degree of regularity of the equation ∑ n i=1 x i = ∑ n i=1 y i + b[END_REF] for a very recent full proof.

Note that the solved case k = 2 of the conjecture and Theorem 1.1 imply a sharp contrast between the additive and the multiplicative versions of the equation,

namely max b dor(L 2 (b)) = 3 versus max b dor(Q(b)) = ∞.

Contents

Here is a brief description of the contents of the paper. In Section 2, we recall some classical problems on partition regularity. In Section 3, after recalling Szemerédi's theorem on arithmetic progressions, we prove our main result on the unboundedness of dor(Q(b)) as b varies. In Section 4, after setting up specific tools for the task at hand, we provide estimates for one of the numbers M(k, δ) involved in Szemerédi's theorem. In Section 5, we determine all b ≥ 1 for which Q(b) is 2-regular, as well as the smallest b ≥ 1 for which Q(b) is 3-regular. The last section is devoted to a few remarks and open questions.

Background

We first recall some background results and problems on partition regularity. The following abridged version of a theorem of Rado [START_REF] Rado | Verallgemeinerung eines Satzes von van der Waerden mit Anwendungen auf ein problem der Zahlentheorie, Sonderausgabe aus den Sitzungsbericten der Preuss[END_REF]10,[START_REF] Rado | Some recent results in combinatorial analysis[END_REF] characterizes the regular linear homogeneous equations on Z.

c 1 x 1 + • • • + c n x n = 0 (3)
is regular if and only ∑ i∈I c i = 0 for some non-empty subset I ⊆ {1, . . . , n}.

One of the main open problems in the linear case is Rado's boundedness conjecture. A simplified version of it states that if equation ( 3) is r-regular for some integer r = r(n) only depending on n, then it is regular. See for instance [START_REF] Fox | On Rado's Boundedness Conjecture[END_REF], where the conjecture is settled for n = 3 with the value r(3) = 24. See also [START_REF] Bialostocki | A zero-sum theorem[END_REF]4,[START_REF] Fox | On the degree of regularity of generalized van der Waerden triples[END_REF] Still less is known in the nonlinear case. For instance, it is an open question whether the quadratic Diophantine equation

x 2 + y 2 = z 2 (4)
is regular. According to a recent preprint using massive computer computations with a SAT solver, equation ( 4) turns out to be 2-regular [START_REF] Cooper | Coloring so that no Pythagorean Triple is Monochromatic[END_REF]. More precisely, for every 2-coloring of the integer interval [START_REF] Adhikari | On a conjecture of Fox and Kleitman on the degree of regularity of a certain linear equation[END_REF]7825], there is a monochromatic solution in that interval to equation (4), and 7825 is minimal in that respect. However, it is not known whether that equation is 3-regular, and it remains an open problem to determine its precise degree of regularity. Note that some other homogeneous quadratic equations in three variables have recently been shown to be regular [START_REF] Frantzikinakis | Higher order Fourier analysis of multiplicative functions and applications[END_REF].

Main result

In this section, we show that the numbers dor(Q(b)) are unbounded as b varies.

Some tools

To start with, for the statement and proof of our main result, we need the deep theorem of Szemerédi about the existence of long arithmetic progressions in sufficiently dense subsets of sufficiently large integer interval [13, p. 244, Corollary].

Theorem 3.1 (Szemerédi). Given a desired length k ∈ N + and a specified density 0 < δ ≤ 1, there exists a positive integer N = N(k, δ) such that every subset A ⊆ [1, N] of density |A|/N ≥ δ contains an arithmetic progression of length k.

For definiteness and in the sequel, we shall denote by M(k, δ) the smallest positive integer N with the above property.

We also need an elementary folklore lemma about the preservation of density under partitions of finite sets.

∑ i |A ∩ E i | < δ ∑ i |E i |. Since ∑ i |A ∩ E i | = |A| and ∑ i |E i | = |E|, the above inequality leads to |A| < δ|E| = |A|, a contradiction.

Unboundedness of dor(Q(b))

Let r ∈ N + be given. For the statement below, we invoke Szemerédi's theorem with the desired length k = r! + 1 and density δ = 1/r. Let N = M(r! + 1, 1/r). Then N has the property that every subset B ⊆ [1, N] of density |B|/N ≥ 1/r contains an arithmetic progression of length r! + 1. Clearly, the same property holds for any integer interval [a, a + N -1] of length N.

Recall that Q(b) denotes the Diophantine equation (

(x 1 -y 1 )(x 2 -y 2 ) = b.
) 5
Not much is known about d besides the inequality r!d ≤ N. As customary in additive combinatorics, let us denote

S -S = {s 1 -s 2 | s 1 , s 2 ∈ S}. Fact 1. We have [1, r!]d ⊆ S -S.
Indeed, for all 1 ≤ j ≤ r!, we have jd = (s + jd)s, and so jd ∈ S -S by [START_REF] Cooper | Coloring so that no Pythagorean Triple is Monochromatic[END_REF]. That is, there exist x 1 , y 1 , x 2 , y 2 ∈ S such that (x 1y 1 )(x 1y 1 ) = N!r!, thus yielding a monochromatic solution of equation Q(N!r!). Therefore this equation is rregular, as claimed.

More properties of dor(Q(b))

The problem of determining dor(Q(b)) as a function of b ∈ N + is probably very difficult. In Section 5.1, we show that dor(Q(b)) ≥ 2 if and only if b ∈ 4N + , thereby improving the case r = 2 of Theorem 3.3. The case r = 3 of that result is improved in Section 5.2, where we show that dor(Q(36)) = 3. We conclude this section with some general properties of dor(Q(b)).

Proposition 3.4. Let b, m ∈ N + . If b ≡ 0 mod m 2 , then dor(Q(b)) ≤ m -1.
Proof. Consider the m-coloring of N + given by the class mod m. That is, color classes correspond to congruence classes mod m. If m 2 does not divide b, then equation (x 1y 1 )(x 2y 2 ) = b has no monochromatic solution under this coloring, for if x 1 , y 1 , x 2 , y 2 are of the same color, i.e., are congruent mod m, then m 2 divides (x 1y 1 )(x 2y 2 ).

For instance, if b is not divisible by 36 = 6 2 , then equation Q(b) is not 3regular, as follows by successively taking m = 2 and m = 3 in the above result.

Proposition 3.5. Let b,t ∈ N + . Then dor(Q(b)) ≤ dor(Q(t 2 b)). Proof. Set r = dor(Q(b)). Let c : N + → [1, r] be an r-coloring. Define a new r-coloring c : N + → [1, r] by setting c (n) = c(tn) for all n ≥ 1. Since Q(b) is r-regular by hypothesis, there is a solution (x 1 , y 1 , x 2 , y 2 ) of equation Q(b) which is monochromatic under c . Hence (tx 1 ,ty 1 ,tx 2 ,ty 2 ) is monochromatic under c. Moreover, since (x 1 -y 1 )(x 2 -y 2 ) = b by hypothesis, it follows that (tx 1 -ty 1 )(tx 2 -ty 2 ) = t 2 b.
Therefore (tx 1 ,ty 1 ,tx 2 ,ty 2 ) is a solution of equation Q(t 2 b), and it is monochromatic under c as already seen. We conclude that Q(t 2 b) is r-regular.

4 On M(3, 1/2) Theorem 3.3 involves the numbers M(r! + 1, 1/r) arising from Szemerédi's theorem. In this section, after setting up some useful tools, we determine this number for r = 2, namely M(3, 1/2).

Detecting arithmetic progressions

Let (G, +) be an abelian group. Here we set up some notation and terminology to help determine the presence or absence of arithmetic progressions of a given length in sequences in G. This will then be used in G = Z to show M(3, 1/2) = 17.

Let A = (a 1 , . . . , a n ) be a sequence in G of length |A| = n. A block in A is any subsequence of consecutive elements, i.e., of the form A[i, j] = (a i , a i+1 , . . . , a j ) for some indices 1 ≤ i, j ≤ n, allowing the empty subsequence if j < i. We denote by σ(A) = ∑ i a i the sum of the elements of A. Definition 4.1. Let A be a finite sequence in G. A block decomposition of A is a sequence (A 1 , . . . , A m ) of consecutive blocks A t of A, 1 ≤ t ≤ m, whose concatenation is A. A contraction of A is a sequence in G of the form (σ(A 1 ), . . . , σ(A m )) where (A 1 , . . . , A m ) is a block decomposition of A. A minor of A is a contraction of a block B of A or, equivalently, a block in a contraction of A.

For instance, if A = (1, 5, 1, 8, 2, 3, 1) in G = Z, then ((1, 5, 1), (8, 2), (3, 1)) is a block decomposition of A and (7, 10, 4) is the corresponding contraction of A. Some minors of A are (6, 1, 8), (7, 10), (9, 5, 1), (10, 3) and (10,4). Note that (6, 1, 8) is a contraction of the block (1, 5, 1, 8) in A, and a block in the contraction (6, 1, 8, 6) of A. Definition 4.2. Let X = (x 0 , x 1 , . . . , x n ) be a sequence in G with n ≥ 1. The discrete derivative of X is its sequence of successive jumps, i.e., ∆(X) = (x 1x 0 , . . . , x nx n-1 ).

For instance, X is an arithmetic progression of length n + 1 in G if and only if ∆(X) is a constant sequence of length n.

Let us now observe that for a sequence X, block sums in ∆(X) correspond to differences of two terms in X. Lemma 4.3. Let X = (x 0 , x 1 , . . . , x n ) be a sequence in G. Let A = ∆(X) = (a 1 , . . . , a n ) where a

i = x i -x i-1 for i ≥ 1. Let B = A[i, j] for some 1 ≤ i ≤ j ≤ n. Then σ(B) = x j -x i-1 . Proof. We have σ(A[i, j]) = ∑ i≤t≤ j (x t -x t-1 ) = x j -x i-1 .
Here is a correspondence between subsequences of X and minors of ∆(X).

Lemma 4.4. Let X be a finite sequence in G. If Y is a subsequence of X, then ∆(Y ) is a minor of ∆(X). Conversely, if C is a minor of ∆(X), then C = ∆(Y ) for some subsequence Y of X. Proof. Let X = (x 0 , x 1 , . . . , x n ) and A = ∆(X) = (a 1 , . . . , a n ) where a i = x i -x i-1 for i ≥ 1. Let Y = (x i 0 , x i 1 , . . . , x i m ) be a subsequence of X, with 0 ≤ i 0 < i 1 < • • • < i m ≤ n. Then ∆(Y ) = (x i 1 -x i 0 , . . . , x i m -x i m-1 ). Let B t = A[i t-1 + 1, i t ] for 1 ≤ t ≤ m. By Lemma 4.3, we have ∆(Y ) = (σ(B 1 ), . . . , σ(B m )). Let B = A[i 0 + 1, i m ]. Then (B 1 , . . . , B m ) is a block decomposition of B. Therefore ∆(Y ) is a contraction of block B

and hence a minor of A.

Conversely, let C be a minor of A. Hence there is a block B in A such that C = (σ(B 1 ), . . . , σ(B m )) for some block decomposition (B 1 , . . . , B m ) of B. For each 1 ≤ t ≤ m, we have B t = A[ j t , i t ] for some 1 ≤ j t ≤ i t ≤ n. Since the B t 's are consecutive blocks in B, and hence in A, we have j t = i t-1 + 1 for t ≥ 2. Thus, denoting i 0 = j 1 -1, we have B t = A[i t-1 + 1, i t ] for all 1 ≤ t ≤ m, and σ(B t ) = x i tx i t-1 by Lemma 4.3. Therefore C = ∆(Y ) where Y = (x i 0 , x i 1 , . . . , x i m ).

This correspondence yields the following convenient tool to determine the presence or absence of arithmetic progressions of a given length in sequences in G. Proposition 4.5. Let X be a finite sequence in G. Then X contains an arithmetic progression of length k ≥ 3 if and only if ∆(X) has a constant minor of length k -1.

Proof. If X contains an arithmetic sequence Y of length k, then ∆(Y ) is a constant sequence of length k -1, and it is a minor of ∆(X) by the preceding lemma. Conversely, let C be a constant minor of length k -1 of ∆(X). Then by the above lemma, there exists a subsequence Y of X such that C = ∆(Y ), and Y is an arithmetic progression of length k since ∆(Y ) is constant of length k -1.

For instance, let X = [START_REF] Adhikari | On a conjecture of Fox and Kleitman on the degree of regularity of a certain linear equation[END_REF]2,4,[START_REF] Cooper | Coloring so that no Pythagorean Triple is Monochromatic[END_REF]10,[START_REF] Rado | Some recent results in combinatorial analysis[END_REF][START_REF] Szemerédi | On sets of integers containing no k elements in arithmetic progression[END_REF][START_REF]Van der Waerden numbers[END_REF] in G = Z. Let A = ∆(X). Then A = (1, 2, 1, 5, 1, 2, 1) and A contains no constant minor of length 2 as easily checked by inspection. Therefore X contains no arithmetic progression of length 3.

Determining M(3, 1/2)

As an application in G = Z, we obtain here the exact value of M(r! + 1, 1/r) for r = 2. Even though the result is easy to obtain by computer, the present method will hopefully, in future works, yield exact values or good bounds in harder cases. Proof. We first claim that the only sequences B in N + such that |B| = 4, σ(B) ≤ 8 and admitting no constant minor of length 2 satisfy σ(B) = 8. More precisely, the only such sequences are, up to reversal, (1, 2, 4, 1) and (2, 1, 4, 1). This is easy. Indeed, let (C 1 ,C 2 ) be a block decomposition of B with

|C i | = 2 for i = 1, 2. Since σ(C 1 ) + σ(C 2 ) = σ(B) ≤ 8
, and no C i can be constant, then each C i concides, up to reversal, with one of the sequences (1, 2), (1, 3), [START_REF] Adhikari | On a conjecture of Fox and Kleitman on the degree of regularity of a certain linear equation[END_REF]4), (2,[START_REF] Bialostocki | A zero-sum theorem[END_REF]. Moreover σ(C 1 ) = σ(C 2 ), for otherwise (σ(C 1 ), σ(C 2 )) would be a constant minor of length 2 of B. Up to reversal of B, we may assume σ(C 1 ) < σ(C 2 ). Hence C 1 = (1, 2) up to reversal, and σ(C 2 ) = 4 or 5. By considering all possible combinations, it is easily seen that C 2 = (4, 1) is the only valid possibility. This proves the claim.

Assume, for a contradiction, that there exists X ⊂ [1, 17] of cardinality |X| = 9 containing no arithmetic progression of length 3. Let A = ∆(X), when X is viewed as an increasing sequence. Then |A| = 8, σ(A) = max(X)min(X) ≤ 16 and A admits no constant minor of length 2. Let (B 1 , B 2 ) be a block decomposition of A with |B 1 | = |B 2 | = 4. Then neither B 1 nor B 2 admits a constant minor of length 2. Moreover, since σ(B 1 ) + σ(B 2 ) = σ(A) ≤ 16, we may assume σ(B 1 ) ≤ 8 up to reversal of A. Hence σ(B 1 ) = 8 by the above claim. Therefore σ(B 2 ) ≤ 8 as well, whence σ(B 1 ) = 8 by the above claim again. But then, (σ(B 1 ), σ(B 2 )) = (8, 8) is a constant minor of length 2 of A, a contradiction. Proof. The proposition yields M(3, 1/2) ≤ 17. In order to establish the equality, we must exhibit, for all 1 ≤ m ≤ 16, a subset X m ⊆ [1, m] of density at least 1/2 and containing no 3-term arithmetic progression. Let X = {1, 2, 4, 5, 10, 11, 13, 14}. Then the set X m defined as follows will do:

X m = X ∩ [1, m] if m = 9 {1, 2, 4, 8, 9} if m = 9.

Comparison with W (k, r)

It would be desirable to determine M(k, 1/r) for more instances of the pair (k, r), as nothing precise seems to be known about these numbers. We have started to make the first few steps towards that objective in a paper under preparation. Of course, these numbers are bounded below by the corresponding van der Waerden numbers. Given integers k, r ≥ 1, recall that the van der Waerden number W (k, r) denotes the least integer M such that, for every r-coloring of [1, M], there is a monochromatic arithmetic progression of length k in [1, M]. Clearly, we have

M(k, 1/r) ≥ W (k, r). (6)
Indeed, let N = M(k, 1/r), and consider any r-coloring of [1, N]. Then some color class X ⊆ [1, N] is of density |X|/N ≥ 1/r, and hence X contains an arithmetic progression of length k, of course monochromatic by construction. The only exactly known van der Waerden numbers at the time of writing are given in the following table. See e.g. [START_REF]Van der Waerden numbers[END_REF], a web page which also displays lower bounds on W (k, r) for many more pairs (k, r).

W (3, 2) = 9 W (3, 3) = 27 W (3, 4) = 76 W (4, 2) = 35 W (4, 3) = 293 W (5, 2) = 178 W (6, 2) = 1132 5 When r is small
In this section, we obtain sharper statements than Theorem 3.3 for r = 2 and 3. We also discuss some corresponding Rado numbers.

The case r = 2

For r = 2, and with the notation of Section 3, our main result states that with N = M(3, 1/2), equation (x 1y 1 )(x 2y 2 ) = 2N! is 2-regular.

We have seen above that M(3, 1/2) = 17. Thus, Theorem 3.3 states that equation Q(2 • 17!) is 2-regular. However, we now show that the same already holds for equation Q( 4 Assume now b ≡ 0 mod 4. First some notation. Let X ⊆ N + be any nonempty subset. We denote D(X) = (X -X) ∩ N, the set of distances in X, and

D 2 (X) = {d 1 d 2 | d 1 , d 2 ∈ D(X)},
the set of products of two distances in X. Thus, equation Q(b) has a solution in X if and only if b ∈ D 2 (X). Finally, we denote X = N + \ X.

Claim 1. If m ∈ N \ D(X), then m + X ⊆ X.
Indeed, for any x ∈ X, we have m = (m + x)x, and since m is not a distance in X, it follows that m + x cannot belong to X.

3. Let t ∈ N satisfy t + X ⊆ X. Then tN ⊆ D(X).
Indeed, the hypothesis implies nt + X ⊆ X for all n ∈ N. Hence, for x ∈ X, we have nt + x ∈ X and so nt = (nt + x)x ∈ D(X).

Let now N

+ = A 0 A 1 be a partition of N + into two nonempty parts. Thus A 1-i = A i for i = 0, 1. We must show that Q(b) has a solution in either A 0 or A 1 or, equivalently, that b ∈ D 2 (A 0 ) ∪ D 2 (A 1 ). Clearly, if D(A i ) = N for i = 0 or 1, we are done since then b ∈ D 2 (A i ). Assume now D(A 0 ), D(A 1 ) = N. Claim 4. Let m ∈ N \ D(A 0 ). Then 2mN + ⊆ D(A 0 ). Indeed, Claim 1 implies m + A 0 ⊆ A 0 = A 1 . (7)
Moreover, Claim 2 implies both D(A 0 ) ⊆ D(A 1 ) and D(A 1 ) ⊆ D(A 0 ). Therefore

D(A 0 ) = D(A 1 ).
Hence m ∈ N \ D(A 1 ), and Claim 1 implies

m + A 1 ⊆ A 0 . (8)
It follows from ( 7) and ( 8) that 2m + A 0 ⊆ A 0 , and then Claim 3 implies

2mN + ⊆ D(A 0 ).
This settles Claim 4. We now examine four possible cases.

Case 1. Assume 1 / ∈ D(A 0 ). Then Claim 4 implies 2N + ⊆ D(A 0 ). Hence 2, b/2 ∈ D(A 0 ), implying b = 2 • b/2 ∈ D 2 (A 0 ).
(A 0 ). But since 1 ∈ D(A 0 ), it follows that b ∈ D 2 (A 0 ). Case 4. Assume 1, 2, b/2 ∈ D(A 0 ). Then b = 2 • b/2 ∈ D 2 (A 0 ).

All four cases lead to the conclusion

b ∈ D 2 (A 0 ). Therefore Q(b) is 2-regular.
Remark 5.2. As easily seen, the 2-color Rado number for equation Q( 4) is equal to 5. That is, for any 2-coloring of [START_REF] Adhikari | On a conjecture of Fox and Kleitman on the degree of regularity of a certain linear equation[END_REF][START_REF] Cooper | Coloring so that no Pythagorean Triple is Monochromatic[END_REF], there is a monochromatic solution to that equation, and 5 is minimal for that property.

The case r = 3

We now show that equation (x 1y 1 )(x 2y 2 ) = 36 is 3-regular. By Proposition 3.4, the right-hand side b = 36 is minimal for that property.

Again, this is a much sharper statement than that provided by Theorem 3.3 for r = 3. Indeed, the number N = M(6! + 1, 1/3) is huge already, since N ≥ W (721, 3) by ( 6), and even more so is the constant term b = 6N! involved in our main result.

As in [2], for a finite sequence A in N + , we denote by bs(A) the set of all signed block sums in A, i.e., bs(A) = {±σ(B) | B is a block in A}.

We shall also need the following ad-hoc definition, specifically tailored to deal with equation Q(36). Of course, it may be easily adapted to deal with equation Q(b) for any b ≥ 1.

Definition 5.3. A sequence A = (a 1 , . . . , a n ) of positive integers is said to be admissible if bs(A) contains no solution of the equation uv = 36, i.e., contains none of the following subsets: {6}, {4, 9}, {3, 12}, {2, 18}, {1, 36}.

Moreover, if A is admissible and σ(A) ≤ t for some integer t, then A is said to be t-admissible. Finally, if A is not admissible then A is said to be forbidden.

For instance, the sequence A = (1, 1, 9, 1) is 12-admissible. Indeed, we have bs(A) ∩ N = {0, 1, 2, 9, 10, 11, 12}, a set containing no subset {u, v} from list (9). Remark 5.4. Every block in a t-admissible sequence is itself t-admissible. A sequence A is admissible if and only if its reverse sequence A is admissible.

In the sequel, as in [2], we say that a set X ⊆ N + is regular with respect to a Diophantine equation D if X contains a solution of D.1 Lemma 5.5. Let X be a finite subset of N + . Let A = ∆(X) be the discrete derivative of X. Then X is regular with respect to equation Q(36) if and only if A is forbidden.

Theorem 2 .

 2 1. (Rado's theorem, abridged version) For n ≥ 2 and c 1 , . . . , c n ∈ Z \ {0}, the Diophantine equation

  for related papers. Other open problems in the linear case concern the m-color Rado number of a given equation. Recall that for a Diophantine equation D, the m-color Rado number R m (D) of D is defined as the smallest positive integer N such that for every m-coloring of [1, N], there is a monochromatic solution in [1, N] to D. If no such N exists, then R m (D) = ∞ by definition.

Lemma 3 . 2 .

 32 Let A ⊆ E be nonempty finite sets. Denote δ = |A|/|E| the density of A in E. Let E = E 1 • • • E r be a partition of E into r nonempty parts. Then there exists an index i ≤ r such that |A ∩ E i |/|E i | ≥ δ. Proof. Assume for a contradiction that |A ∩ E i |/|E i | < δ for all i ≤ r. Then |A ∩ E i | < δ|E i | for all i ≤ r and, summing over i, we get

Theorem 3 . 3 .

 33 Let r ∈ N + , and let N = M(r! + 1, 1/r) be as defined above. Then the Diophantine equation Q(N!r!) is r-regular. Proof. Let ∆ be an arbitrary r-coloring of the integer interval E = [1, (r + 1)N!]. Then there exists a color class S ⊆ E of density |S|/|E| ≥ 1/r. Let us partition E into subintervals of length N, as is possible since N divides |E|. By Lemma 3.2, there exists one such subinterval A ⊆ E of size |A| = N such that |S ∩ A|/|A| ≥ 1/r. By the defining property of N, the subset S ∩ A contains an arithmetic progression of length r! + 1, with common difference d for some d ≥ 1. Thus, there exists s ∈ S ∩ A such that {s, s + d, . . . , s + r!d} ⊆ S ∩ A.

  Set m = N!/d. Partition E into its classes mod m, and then partition each class mod m into subsets of cardinality r +1 of the form C = {a, a+m, . . . , a+rm} ⊂ E. This is possible since m divides |E| and r + 1 divides |E|/m. By Lemma 3.2 again, for at least one such subset C, we must have |S ∩ C|/|C| ≥ 1/r. But since |C| = r + 1, this implies |S ∩C| ≥ 2. Thus, there exist two distinct indices 0 ≤ i < j ≤ r such that a + im, a + jm ∈ S ∩C.

Fact 2 .

 2 We have um ∈ S -S for some u ∈[1, r]. Indeed, simply take um = (a + jm) -(a + im) for the two elements in S ∩C found above. Note that 1 ≤ u = ji ≤ r, as desired. We now combine the above facts. Since m = N!/d, by Fact 2 we have uN!/d ∈ S -S for some u ∈ [1, r]. Now since u divides r!, we have r!/u ∈ [1, r!], and hence (r!/u)d ∈ [1, r!]d. Therefore (r!/u)d ∈ S -S by Fact 1. Multiplying these two elements of S -S together, it follows that N!r! ∈ (S -S)(S -S).

Proposition 4 . 6 .

 46 Every subset X ⊂[START_REF] Adhikari | On a conjecture of Fox and Kleitman on the degree of regularity of a certain linear equation[END_REF] 17] of cardinality |X| = 9 contains an arithmetic progression of length 3.

Corollary 4 . 7 .

 47 We have M(3, 1/2) = 17.

Proposition 5 . 1 .

 51 ), and more generally for equationQ(b) whenever b ∈ 4N + . The equation (x 1y 1 )(x 2y 2 ) = b is 2-regular if and only if b is a multiple of 4.Proof. Proposition 3.4 implies that if b ≡ 0 mod 4, then Q(b) is not 2-regular.

Claim 2 .

 2 If D(X) = N, then D(X) ⊆ D(X). Indeed, let d ∈ D(X). Then d = xy for some x, y ∈ X with x ≥ y. Let now m ∈ N \ D(X). Then d = (m + x) -(m + y), and m + x, m + y ∈ X by Claim 1. Hence d ∈ D(X).

Claim

Case 2 .

 2 Assume 1 ∈ D(A 0 ) and 2 / ∈ D(A 0 ). Then Claim 4 implies 4N + ⊆ D(A 0 ). Hence b ∈ D(A 0 ), and since 1 ∈ D(A 0 ) it follows that b ∈ D 2 (A 0 ). Case 3. Assume 1 ∈ D(A 0 ) and b/2 / ∈ D(A 0 ). Then Claim 4 implies b ∈ D

3 . 4 .

 34 Given r ≥ 1, what is the smallest b = b(r) such that Q(b) is r-regular? Theorem 3.3 provides the upper bound b(r) ≤ M(r! + 1, 1/r)!r! but, as observed in cases r = 2 and 3, this is very far from being optimal. We have seen that b(2) = 4 and b(3) = 36. What is b(4), for instance? More generally, what is the expected growth of b(r) as a function of r? Given r, b ≥ 1, what is the r-color Rado number of equation Q(b)? In this paper, we provided the answer for the pairs (r, b) = (2, 4) and (3, 36).

That is, if there is some solution (x 1 , . . . , x n ) of D with x i ∈ X for all i.

we may assume |X| = 13. Let B = ∆(X), the discrete derivative of X when X is viewed as an increasing sequence. Then B is of length 12, and B satisfies σ(B) = max Xmin X ≤ 36. Then B is not admissible by the above claim. Hence B is regular with respect to Q(36) by Lemma 5.5.

Corollary 5.8. We have dor(Q(36)) = 3. Moreover, for all t ∈ N + , equation Q(36t 2 ) is 3-regular.

Proof. We have dor(Q(36)) ≥ 3 by the above corollary, and dor(Q(36)) ≤ 3 by Proposition 3.4. The second assertion follows from the 3-regularity of Q(36) and Proposition 3.5.

Corollary 5.9. The 3-color Rado number for equation Q(36) is equal to 37.

Proof. Let R denote the 3-color Rado number for Q(36). We have R ≤ 37, since Corollary 5.7 implies that for every 3-coloring of [START_REF] Adhikari | On a conjecture of Fox and Kleitman on the degree of regularity of a certain linear equation[END_REF]37], there will be a monochromatic solution of Q(36). To see that R ≥ 37, it suffices to exhibit a 3-coloring of [START_REF] Adhikari | On a conjecture of Fox and Kleitman on the degree of regularity of a certain linear equation[END_REF]36] admitting no monochromatic solution to Q(36). Here is such a coloring, the three color classes being as follows:

Concluding remarks

Several problems related to the contents of this paper remain widely open and would deserve further investigation. Here is a short selection.

What is the degree of regularity of equation Q(b) as a function of b?

We showed here that, as b varies, the numbers dor(Q(b)) are both finite and unbounded.

2. Given r ≥ 1, can one determine all b ∈ N + such that dor(Q(b)) = r? For r = 2, our answer is all b ≡ 0 mod 4. For r ≥ 3, can one similarly expect the answer to be given by suitable congruence classes? For instance, for r = 3, is the answer given by b ≡ 0 or ±36 mod 180? We don't know, but some preliminary indices point to an answer of this type.

Authors' addresses:

• S. D.