One for the sake of two.

Number Theory Level 2

To every two integers (A , B) we can assign a third integer like their sum A+B, or their product.

But here is a more interesting question. How about a different integer for every A and B ? You can see that sums and products don't work anymore because the pairs (2,1) and (9,-6) have the same sum, for example...

Is there a general method to assign a different number to every pair (A , B) ?

Yes Nobody knows. There exists such a method but nobody has found it yet. It's impossible.

3 solutions

Brian Moehring
Jul 31, 2018

Here's one way to do it.

First define the signum function $\text{sgn}(n) = \begin{cases}1 & n > 0 \\ 0 & n=0 \\ -1 & n<0\end{cases}$

Then to each pair $(m,n),$ we assign the number $2^{3|m|+\text{sgn}(m)} \times 3^{3|n|+\text{sgn}(n)}$

To show this is valid, you just need to show that the map taking $m$ to $3|m|+\text{sgn}(m)$ assigns a unique non-negative integer to each integer. Then the result for the above map on the pair $(m,n)$ follows immediately by the fundamental theorem of arithmetic.

As an interesting extension, note that a similar map can be made for any given length tuples $(n_1, n_2, n_3, \ldots, n_k)$ of integers, assigning each a unique positive integer. In fact, it works for the set of infinite sequences of integers $(n_1, n_2, n_3, \ldots)$ as long as every sequence is eventually zero.

How about this ? Assign a different integer to every polynomial with algebraic coefficients.

Arousse Fares - 2 years, 10 months ago

The map would be horribly complicated, but there definitely is such a map.

Brian Moehring - 2 years, 10 months ago

Actually you could just apply my solution to the original problem ^^ : You first write the polynomial in letters, convert them in numbers and between each two letters you put a 0 and between each two words you put a 00. You then have it !

Arousse Fares - 2 years, 10 months ago

@Arousse Fares – What this actually defines (at least, after fixing a slight issue with encoding 'J' and 'T') is a surjective map from a subset of the natural numbers to the set of polynomials with algebraic coefficients.'

The process of going from this map to one that assigns a unique integer to each polynomial requires one of the following:

A constructible function from the set of algebraic numbers to the set of descriptions of the computable numbers, and while I have no proof of its nonexistence, I would be quite surprised if such a function exists.
A nonconstructive step using the axiom of choice.

Brian Moehring - 2 years, 10 months ago

@Brian Moehring – I'm not sure I totally grasp the notion of "constructible functions".

Here is what wikipedia says : a time-constructible function is a function f from natural numbers to natural numbers with the property that f(n) can be constructed from n by a Turing machine in the time of order f(n)

What I understand is that you want a way to guarantee that each and every polynomial will be dealt with in a finite time. I hope it wasn't too wrong of an approximation ^^.

The polynomials can be represented by their Roots only. So P := (R1 , R2 , ... Rn)

The roots are algebraic numbers.

Algebraic numbers are roots of polynomials with integer coefficients. So every algebraic number can be represented by a finite list of integers. We also have to make sure that the same algebraic number doesn't appear twice in two different lists. Was this the "nonconstructive step using the axiom of choice" you were speaking of ? Indeed, I can't find a way to deal with this matter in a finite time... ^^. So yeah, I'll leave it to the axiom of choice. (But we can find ways to minimize its use, although there is no guarantee that an action won't take endless time...)

After finding a way to assign a different finite list to each algebraic number, we just have to count all the combinations and encode each combination as we do so.

No mistakes ?

Arousse Fares - 2 years, 10 months ago

@Arousse Fares – I wasn't actually aware of the use of the term "constructible function" in computation theory. All I meant, informally, is a specific function that has a finite definition which allows it to specify a unique description for each algebraic number.

The nonconstructive step I mentioned was in creating an "inverse" to the function I was talking about when I said "What this actually defines (at least, after fixing a slight issue with encoding 'J' and 'T') is a surjective map from a subset of the natural numbers to the set of polynomials with algebraic coefficients." This is because, unless we can provide a rule to choose an "inverse", we would need to use the following:

If $A,B$ are sets and $f : A \to B$ is a total surjective function, then there is a total injective function $g : B \to A$ such that $f \circ g = \text{id}_B$ is the identity function on $B$ .

which (if I recall correctly) is equivalent to the axiom of choice.

That all said, apparently my mind kept on thinking about this problem as I slept, as I woke up with a way to assign a unique integer to each polynomial with algebraic coefficients. Here's how:

Given any nonzero polynomial with algebraic coefficients $q(x) = \sum_{k=0}^N A_k x^k$ where $A_N \neq 0$ , we define the map $F$ by $F(q) = (N, A_N, A_{N-1}, \ldots , A_1, A_0)$

Now, given any algebraic number $A$ , there is a unique irreducible polynomial $p$ with integer coefficients such that the coefficients are coprime, the leading coefficient is positive, and $p(A)=0$ . Also, if we let $B_1, \ldots, B_m$ denote the other roots of $p$ , then there is a minimal non-negative integer $n$ such that $\lfloor 10^n\text{Re}A\rfloor \neq \lfloor 10^n\text{Re}B_i\rfloor$ or $\lfloor 10^n\text{Im}A\rfloor \neq \lfloor 10^n\text{Im}B_i\rfloor$ for all $i$ . This allows us to encode $A$ as $G(A) = \left(F(p), n, \lfloor 10^n\text{Re}A\rfloor, \lfloor 10^n\text{Im}A\rfloor\right)$

Using all this, we can encode the polynomial $q$ I mentioned above as the tuple $(N, G(A_N), G(A_{N-1}), \ldots, G(A_1), G(A_0))$ which can be naturally injected into the set of sequences of integers that converge to zero. (The natural map I'm talking about isn't automatically an injection... it's due to the fact the first entry in each element in the range of $F$ , and therefore each element in the range of $G$ , tells how many entries that element has)

Then we can just take the encoding I referenced in the problem as $(n_1, n_2, n_3, \ldots) \mapsto \prod_{k=1}^\infty p_k^{3|n_k| + \text{sgn}(n_k)}$ where $p_k$ is the $k$ th prime number.

The only polynomial we can't use this process on is the zero polynomial, but since there's no way to write the number zero as a product of primes, obviously it isn't in the range of the given encoding, so just map the zero polynomial to the number zero.

Brian Moehring - 2 years, 10 months ago

@Brian Moehring –

When you said :

F(q) = (N , A_{n} , A_{n-1} , ... , A_{1} , A_{0})

Is there a reason in including the degree of the polynomial in your map ?

An other way to map for $G(A)$ :

Now, given any algebraic number $A$ , there is a unique irreducible polynomial $p$ with integer coefficients such that the coefficients are coprime, the leading coefficient is positive, and $p(A)=0$ . Also, if we let $B_1, \ldots, B_m$ denote the other roots of $p$ , then for every tuple $(B_1, \ldots, B_m)$ we can assign a unique integer (using your encoding of course because it would be cool to make it do everything ). Then we just proceed with the solution.

Does it work ?

Arousse Fares - 2 years, 10 months ago

@Arousse Fares – With the natural map I mentioned in the last part of my post, both $\Big(3, (6,3,2), (77,-3,5,2,2), 5, 3, (26,55)\Big) \\ \Big((3, 6), 3, (2, 77, -3, 5), (2,2,5,3,26), 55\Big)$ would be mapped to $\Big(3, 6, 3, 2, 77, -3, 5, 2, 2, 5, 3, 26, 55,0,0,0,0,0,0,0,0,\ldots\Big)$ which means it's not injective, so the final assignment of an integer wouldn't be unique.

There are two standard ways to resolve this:

The method I chose to use: the first entry in each tuple $G(A_i)$ contains information about how long the original tuple was. Then, even after we apply that natural map, the original tuple of tuples can be recovered, so the natural map would be injective on the set of admissible tuples.
Call the function that encodes arbitrary length tuples $e$ . Then encode each $G(A_i)$ as $e(G(A_i))$ and then encode again as $e\Big(e(G(A_N)), e(G(A_{N-1})), \ldots, e(G(A_1)), e(G(A_0))\Big).$ Since we never need to use that natural map I mentioned, we don't lose any information here, so there's no need to keep track of the degrees in this case.

These are analogous to nested loops or a two-step recursion, respectively. I just prefer to use loops when I don't need recursion, but otherwise, there's no reason to prefer one method over the other.

For your definition of $G$ , you seem to be begging the question. The whole problem that $G$ is trying to solve is to assign a tuple of integers uniquely to each algebraic number, so without first defining $G$ for a single algebraic number, how would we go about encoding a tuple of algebraic numbers? Then, even if we could do that, how would we recover the algebraic number $A$ ?

In case I wasn't clear, my $G$ first uniquely identifies the minimal polynomial for $A$ over the integers, but then we have the problem of uniquely differentiating $A$ from all of its conjugates $B_1, B_2, \ldots, B_m$ . To do this, I note that two numbers are different if they differ at some point in their decimal expansion, so we let $n$ be least number of digits required after the decimal point, and then I give the all the required digits in both the real and imaginary parts of $A$ .

Brian Moehring - 2 years, 10 months ago

@Brian Moehring – Alright. So I get how your function works but I guess I need some time to "digest" it.

As to how to assign a unique integer to every algebraic number :

Given any algebraic number $A$ , there is a unique irreducible polynomial $p$ with integer coefficients such that the coefficients are coprime, the leading coefficient is positive, and $p(A)=0$ . Also, let $B_1, \ldots, B_m$ denote the roots of $p$ , let $c_1, c_2, c_3, \ldots, c_n$ be the coefficients and let $B_i = A$

Let $K$ be the name of the function $(n_1, n_2, n_3, \ldots) \mapsto \prod_{k=1}^\infty p_k^{3|n_k| + \text{sgn}(n_k)}$

then the map goes like this :

$B_i \mapsto K ( K( c_1, c_2, c_3, \ldots, c_n ) , i)$

The good thing your function is that order matters ^^. If we want to map all polynomials with algebraic coefficients to an integer, we just have to map the integers you obtain from the algebraic numbers. And again, since order matters in your function, we will always get a different integer.

So ? :p

Arousse Fares - 2 years, 10 months ago

@Arousse Fares – Almost there. We just have to choose a total order on the set of algebraic numbers in order to define the ordering of $B_1, B_2,\ldots,B_m$ (We can't choose each arbitrarily without the axiom of choice). Luckily, there's a few predefined total orders to choose from: e.g. lex, revlex, etc., or just define one of your own.

Once we fix a total order, $i$ is well-defined given any $A$ .

I like revlex but the choice itself doesn't matter, only that a choice is made that covers all algebraic numbers.

Brian Moehring - 2 years, 10 months ago

@Brian Moehring – Actually, how about this ? Algebraic numbers are countable so you can choose a way to count them and make a sequence of it. You can then assign the algebraic number to the first time it appears in that sequence.

Please, tell me this is wrong.

Arousse Fares - 2 years, 10 months ago

@Arousse Fares – It's not wrong in the sense of being false, but for our purposes, it is wrong in the sense of being an invalid argument.

The whole point in defining $G$ is to define a function that counts the algebraic numbers, so using a cardinality argument to imply the existence of such a function is begging the question and doing so in a manner that makes explicit construction of a map counting the polynomials with algebraic coefficients impossible.

Brian Moehring - 2 years, 10 months ago

@Brian Moehring – Alright, I got it. Thank you, that was fun !

Arousse Fares - 2 years, 10 months ago

Michael Mendrin
Jul 31, 2018

If by "number" we can use irrationals, then for integers $A, B$ assign $A+B\sqrt{2}$ . Given any other pair of integers $C, D$

$A+B\sqrt{2} \ne C+D\sqrt{2}$

If numbers are restricted to integers, see Brian Moehring's solution.

Since it was precised on the first line, and since the second line was directly related to the first, I thought that the title "integer" was still addressed to the number... guess It doesn't work like that. ^^

Arousse Fares - 2 years, 10 months ago

It never hurts to eliminate ambiguity, because that is a problem with a lot of contributed problems. I've been burned by too many problems that have relied on "thinking outside assumptions".

Michael Mendrin - 2 years, 10 months ago

Arousse Fares
Jul 31, 2018

You sure can !

There are several rigorous ways to answer the problem but here is a home made solution :

Step 1 : You write the pair in letters.

(5,4) becomes : Five and four

Step 2 : You correspond every letter by its position in the alphabet.

A : 1

B : 2

J and T can be 27 and 28 ! ...

and you use 0 to separate between every two letters and 00 between every two words. Five and four becomes 6090220500101404006015021018 And you have it.

One for the sake of two.

3 solutions

0 pending reports