Combinatorial principles in elementary number theory

DOI10.1016/0168-0072(91)90096-5MaRDI QIDQ1182430zbMATH OpenOpenAlexFDO

Authors Alessandro Berarducci, Benedetto Intrigila

Publication date 28 June 1992

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(91)90096-5

zbMATH Keywords

\(\Delta_ 0\)- equipartition principle\(\hbox{I}\Delta_ 0\)combinatorial principleLagrange four squares theoremweak \(\Delta_ 0\)-pigeonhole principle

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Primes (11A41)

Review text

It is shown that the theory \(\hbox{I}\Delta_ 0\;+\) weak version of the \(\Delta_ 0\)-Pigeonhole Principle proves the Lagrange four squares theorem. This answers positively a question of A. McIntyre (1986). The authors consider also the number-theoretical consequences of a new combinatorial principle called ``\(\Delta_ 0\)-Equipartition Principle \((\Delta_ 0 \hbox{EQ})\). In particular, a new proof (which can be formalized in \(\hbox{I}\Delta_ 0+\Delta_ 0 \hbox{EQ})\) of the fact that every prime of the form \(4n+1\) is the sum of two squares is given.

Recommendations

• scientific article; zbMATH DE number 863489
• Combinatorial and geometrical investigations in elementary number theory
• scientific article; zbMATH DE number 1474019
• scientific article; zbMATH DE number 1834799
• scientific article; zbMATH DE number 3477291
• Combinatorial Etudes and Number Theory
• A combinatorial theorem in number theory
• scientific article; zbMATH DE number 3414378

Cites work

• Classes of Predictably Computable Functions
• Existence and feasibility in arithmetic
• scientific article; zbMATH DE number 3845576 (Why is no real title available?)
• scientific article; zbMATH DE number 3912375 (Why is no real title available?)
• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 3784875 (Why is no real title available?)
• scientific article; zbMATH DE number 3552620 (Why is no real title available?)
• scientific article; zbMATH DE number 3083488 (Why is no real title available?)
• On the scheme of induction for bounded arithmetic formulas
• Primes and their residue rings in models of open induction
• Provability of the pigeonhole principle and the existence of infinitely many primes

Cited in

(18)

• The prime number theorem and fragments of PA
• Toward the limits of the Tennenbaum phenomenon
• \(\text{Count}(q)\) does not imply \(\text{Count}(p)\)
• End extensions of models of linearly bounded arithmetic
• Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms
• Non-standard finite fields over \(I\Delta_0+\Omega_1\)
• On Grzegorczyk induction
• Quadratic forms in models of \(I\Delta _{0}+\Omega _{1}\). I
• scientific article; zbMATH DE number 5666905 (Why is no real title available?)
• Two (or three) notions of finitism
• On bounded arithmetic augmented by the ability to count certain sets of primes
• Solving Pell equations locally in models of IΔ₀
• Some combinatorial principles defined in terms of elementary submodels
• Lagrange's theorem for binary squares
• Some Elementary Congruences for the Number of Weighted Integer Compositions
• A new proof of the weak pigeonhole principle
• Quadratic forms in models of \(I\Delta_0 + \Omega_1\). II: Local equivalence
• Integer factoring and modular square roots

This page was built for publication: Combinatorial principles in elementary number theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1182430)