An open approach to mathematical optimization, implementation in C and Rust to generate a Collatz trace and check its veracity using polynomial constraints.
You will find two programs one in C another one in Rust. Their structure differs very little and they do the same thing, the goal being to make this research accessible to all. We try here to have a first approach of the notion of polynomial constraints. This program will allow you to generate a sequence of Collatz and come up with polynomial constraints of the respect of the conjuncture. I was inspired by this article (https://medium.com/starkware/arithmetization-i-15c046390862) that I recommend in order to have a more global vision of the subject.
- Introduction 🔮
- Features ⭐️
- Installation ⚒️
- Usage ⚙️
- Contributing 🤝
- License 📃
The Collatz sequence, also known as the 3n+1 sequence, is a series of numbers generated by repeatedly applying the Collatz rule. Starting with a positive integer, if the number is even, divide it by 2; if it's odd, multiply it by 3 and add 1. The sequence continues until it reaches 1. (4, 2, 1, 4, 2, 1...) 🔄 This program allows you to generate the Collatz sequence for a given positive integer and performs various checks on the sequence to validate specific criteria. ✅
The set of criteria is as follows 📐:
Let’s say A Collatz trace starting with x ∈ ℕ* and ending with 1. Then the length of the trace is defined as the number of iterations before reaching 1, noted n, on the other is the number of numbers of the trace. Let q be the largest number of the trace and let m be the number of bits needed for its binary writing. We can then represent this matrix in the form of bits such that A is of size (m x n).
We then have the following polynomial constraints for (n, m):
To simplify the task I took the liberty of modifying the method slightly in my code but we always check the same thing.
Polynomial constraints allow us to obtain information on certain sequences, for example by searching for recurring patterns. More widely they are used in ZKP to express the relations between the secret data of the prover and the public data known by the verifier. It is therefore essential to master this aspect of optimization on (apparently) simple problems such as Collatz. 🧠 The heart of my approach is here, it is up to you to find other criteria and play with them. For my French speakers have a look 👀: https://www.youtube.com/watch?v=BP2G28694z8.
- Generates the Collatz sequence for a given positive integer.
- Performs the following checks on the generated sequence:
- Criterion 1 (🔍): Verifies that the difference between the first binary value and its decimal equivalent is zero.
- Criterion 2 (🔍): Checks if the difference between the last binary value and 1 is zero.
- Criterion 3 (🔍): Validates that all values in the sequence are valid binary numbers (containing only '0' and '1').
- Criterion 4 (🔍): Check the connection between the numbers two by two.
- Provides informative error messages for invalid input or conversion failures.
-
Clone this repository to your local machine:
git clone https://github.com/izCRV/Collatz_Conjecture
For Rust 🦀:
-
Navigate to the project directory.
-
Build and run the program using the Cargo command:
cargo run
-
Enter a positive integer when prompted.
-
The program will display the generated Collatz sequence and perform the checks on the sequence.
For C 🦍:
- Navigate to the project directory.
- Use the command:
make- To get a trace use:
./collatz_proof 'any number > 0'- Copy the output of the terminal.
- Type the command and enter the trace obtained:
./collatz_verif 'ctrl+shitf+v'Contributions to this project are welcome! If you find a bug or want to suggest an enhancement, please open an issue or submit a pull request.
Source : https://medium.com/starkware/arithmetization-i-15c046390862
This project is licensed under my self😎 free to do what you want with it.