/All/
|
index
catalog
recent
update
post
|
/math/
/tech/
/misc/
/free/
/meta/
/test/
|
Guide
light
mod
Log
P47540
Wed 2023-06-07 15:46:12
link
reply
b9abf4154ea361cf890d92405ad06cf12067abca395499a3059ff2774928af62.webp
124 KiB 1280x720
Veritasium recently released a pop-math video on p-adic numbers (and n-adic numbers, the case where the base is not prime). Technically it would be more correct to say he covered p-adic/n-adic
[bold:
integers
]
, since he ignored the cases where the numbers have finitely many digits after the radix point.
https://www.veritasium.com/videos/2023/6/6/the-most-useful-numbers-youve-never-heard-of
/watch?v=tRaq4aYPzCc
If you've studied a lot of math you're probably already aware of p-adics. Otherwise it may seem kind of schizo. But in the video he shows how to add, negate, and multiply n-adic integers.
[bold:
Challenge
]
: Can you prove that the algorithms shown in the video obey the familiar rules of working with numbers
>(a+b)+c=a+(b+c), a+0=a, a+(-a)=0, a+b=b+a,
>(a*b)*c=a*(b*c), a*(b+c)=a*b+a*c, (a+b)*c=a*c+b*c
>a*1=a, 1*a=a, a*b=b*a
or in other words, that the n-adic integers are a commutative ring with identity?
P47544
Wed 2023-06-07 18:00:07
link
reply
sorry, dont really care about yt soymen
Referenced by:
P49938
P50063
P47550
Wed 2023-06-07 19:24:21
link
reply
I do not have much of formal math education, but most of these seem pretty obvious.
If you describe an n-adic integer as a sequence of any numbers continuing infinitely on the left-hand side then the
>a+0=a
would mean
[tex:
... + a
_
3
*n
^
2
+ a
_
2
*n
^
1
+ a
_
1
*n
^
0
]
+ 0
which yields
[tex:
... + a
_
3
*n
^
2
+ a
_
2
*n
^
1
+ (a
_
1
*n
^
0
+ 0)
]
I'd assume that for any digit that +0 would mean nothing meaning the original number remains.
>a+(-a)=0
Following the video, -a would mean
[tex:
... + (9-a
_
3
)*n
^
2
+ (9-a
_
2
)*n
^
1
+ (9-a
_
1
)*n
^
0
]
+ 1]
meaning a+(-a) = 0 forms:
[tex:
... + (a
_
3
+ 9 - a
_
3
)*n
^
2
+ (a
_
2
+ 9 - a
_
2
)*n
^
1
+ (a
_
2
+ 9 - a
_
2
)*n
^
0
]
+ 1 = 0
[tex:
... 9*n
^
2
+ 9*n
^
1
+ 9*n
^
0
]
+ 1 = 0
Which just resolves to 0 with the 1 infinitely carrying over.
>a+b=b+a
Using the above formulation of an n-adic this would mean
[tex:
... + (a
_
3
+b
_
3
)*n
^
2
+ (a
_
2
+b
_
2
)*n
^
1
+ (a
_
1
+b
_
1
)*n
^
0
]
=
[tex:
... + (b
_
3
+a
_
3
)*n
^
2
+ (b
_
2
+a
_
2
)*n
^
1
+ (b
_
1
+a
_
1
)*n
^
0
]
So essentially for any elements
[tex:
a
_
i
]
and
[tex:
b
_
i
]
addition needs to be commutative. For that I can say that when I'm refering to any [x_i] it is an integer such that [x_i mod n = x_i] so this should work.
>a*(b+c)=a*b+a*c
Multiplication for example for n-adic numbers x and y should work like the following.
[tex:
(... + x
_
3
*n
^
2
+ x
_
2
*n
^
1
+ x
_
1
*n
^
0
) * (... y
_
3
*n
^
2
+ y
_
2
*n
^
1
+ y
_
1
*n
^
0
)
]
[tex:
... + (y
_
1
* x
_
m
+ y
_
2
* x
_
{
m-1
}
.. + y
_
m
* x
_
1
) * n
^
{
m-1
}
+ .. + (y
_
1
* x
_
3
+ y
_
2
* x
_
2
+ y
_
3
* x
_
1
) * n
^
2
+ (y
_
1
* x
_
2
+ y
_
2
* x
_
1
) * n
^
1
+ (y
_
1
* x
_
1
) * n
^
0
]
now taking x = a and y = b+c
[tex:
... + ((b
_
1
+c
_
1
) * a
_
m
+ (b
_
2
+ c
_
2
) * a
_
{
m-1
}
.. + (b
_
m
+c
_
m
) * a
_
1
) * n
^
{
m-1
}
+ .. + ((b
_
1
+c
_
1
) * a
_
3
+ (b
_
2
+c
_
2
) * a
_
2
+ (b
_
3
+c
_
3
) * a
_
1
) * n
^
2
+ ((b
_
1
+c
_
1
) * a
_
2
+ (b
_
2
+c
_
2
) * a
_
1
) * n
^
1
+ ((b
_
1
+c
_
1
) * a
_
1
) * n
^
0
]
Now if
[tex:
a
_
i
]
,
[tex:
b
_
i
]
, and
[tex:
c
_
i
]
are integers then
[tex:
a
_
i
*(b
_
i
+c
_
i
) = a
_
i
*b
_
i
+ a
_
i
*c
_
i
]
should be met, and the terms could be factored out
[tex:
... + (b
_
1
*a
_
m
+c
_
1
*a
_
m
+ b
_
2
*a
_
{
m-1
}
+c
_
2
*a
_
{
m-1
}
.. + b
_
m
*a
_
1
+c
_
m
*a
_
1
) * n
^
{
m-1
}
+ .. + (b
_
1
*a
_
3
+c
_
1
*a
_
3
+ b
_
2
*a
_
2
+c
_
2
*a
_
2
+ b
_
3
*a
_
1
+c
_
3
*a
_
1
) * n
^
2
+ (b
_
1
*a
_
2
+c
_
1
*a
_
2
+ b
_
2
*a
_
1
+c
_
2
*a
_
1
) * n
^
1
+ (b
_
1
*a
_
1
+c
_
1
*a
_
1
) * n
^
0
]
[tex:
(... + (b
_
1
*a
_
m
+ b
_
2
*a
_
{
m-1
}
.. + b
_
m
*a
_
1
) * n
^
{
m-1
}
+ .. + (b
_
1
*a
_
3
+ b
_
2
*a
_
2
+ b
_
3
*a
_
1
) * n
^
2
+ (b
_
1
*a
_
2
+ b
_
2
*a
_
1
) * n
^
1
+ (b
_
1
*a
_
1
) * n
^
0
) + (... + (c
_
1
*a
_
m
+ c
_
2
*a
_
{
m-1
}
.. + c
_
m
*a
_
1
) * n
^
{
m-1
}
+ .. + (c
_
1
*a
_
3
+ c
_
2
*a
_
2
+ c
_
3
*a
_
1
) * n
^
2
+ (c
_
1
*a
_
2
+ c
_
2
*a
_
1
) * n
^
1
+ (c
_
1
*a
_
1
) * n
^
0
)
]
or
[tex:
a*b + a*c
]
This is getting long and I'm not even sure if I'm doing the right thing. But anyways such properties of n-adics seem to depend if their digits meet those properties as well. I mean form the definition of addition at least the (a+b)*c=a*c+b*c seems to be met already.
>a+b
[tex:
... + a
_
3
*n
^
2
+ a
_
2
*n
^
1
+ a
_
1
*n
^
0
]
+
[tex:
... + b
_
3
*n
^
2
+ b
_
2
*n
^
1
+ b
_
1
*n
^
0
]
-------------------------------------------
[tex:
(a
_
3
+b
_
3
)*n
^
2
+ (a
_
2
+b
_
2
)*n
^
1
+ (a
_
1
+b
_
1
)*n
^
0
]
and since carries exist if
[tex:
a
_
i
+ b
_
i
> n-1
]
then if
[tex:
a
_
i
+ b
_
i
= c
_
i
+ d
_
i
* n
]
:
[tex:
(a
_
i
+b
_
i
)*n
^
m
= (d
_
i
)*n
^
{
m+1
}
+ (c
_
i
)*n
^
m
]
meaning
[tex:
(c
_
i
+ d
_
i
*n)*n
^
m
= (d
_
i
)*n
^
{
m+1
}
+ (c
_
i
)*n
^
m
]
and that at least the (a+b)*c=a*c+b*c and/or a*(b+c)=a*b+a*c works for the digits. Maybe this is the actual way you are supposed to prove them rather than just assuming that the rules are met automatically.
(Sidenote: d_i is going to be 1 as a digit m must meet
[tex:
m mod n = m
]
meaning with any n-adic system the largest number is going to be 2*(n-1) meaning a max carry of 1 as 2n-2 < 2n
Referenced by:
P47555
P50045
P47551
Wed 2023-06-07 19:28:28
link
reply
>...999999999999=-1
It's amusing that this works similarly to 2's complement integers. Do computers work with truncated 2-adics? What other properties of the 2-adics can be transposed there?
Oh, he actually uses the term "9's complement"
How come their are no other measures of distance with "good properties" than the three he described? (the usual absolute value, the p-adic and the one where L(0)=0 and L(x≠0)=k>0)
In the tri-force looking representation, are the holes the irrational numbers?
To answer your challenge, the additions are pretty much trivial
>(a+b)+c=a+(b+c)
Let's note
[tex:
a = a
_
0
+ p a
_
1
+ p
^
2
a
_
2
+ ...
]
, [b = b_0 + p b_1 + p^2 b_2 + ...] and so on, then
[tex:
(a+b)+c = ((a
_
0
+b
_
0
) + p (a
_
1
+b
_
1
) + p
^
2
(a
_
2
+b
_
2
) + ...) + c = (a
_
0
+b
_
0
+c
_
0
) + p (a
_
1
+b
_
1
+c
_
1
) + p
^
2
(a
_
2
+b
_
2
+c
_
2
) + ...
]
and
[tex:
a+(b+c) = a + ((c
_
0
+b
_
0
) + p (c
_
1
+b
_
1
) + p
^
2
(c
_
2
+b
_
2
) + ...) = (a
_
0
+b
_
0
+c
_
0
) + p (a
_
1
+b
_
1
+c
_
1
) + p
^
2
(a
_
2
+b
_
2
+c
_
2
) + ...
]
>a+0=a
[tex:
a+0 = a
_
0
+0 + p (a
_
1
+0) + p
^
2
(a
_
2
+0) + ... = a
]
>a+(-a)=0
If we take
[tex:
(-a) = 1 + ((p-1)-a
_
0
) + p ((p-1)-a
_
1
) + p
^
2
((p-1)-a
_
2
) + ...
]
then
[tex:
a+(-a) = 1 + (p-1) + p(p-1) + p
^
2
(p-1) + ... = p + p(p-1) + p
^
2
(p-1) + ... = p
^
2
+ p
^
2
(p-1) + ...
]
We can see that this will simplify to ...0000, but this doesn't convince me still.
More formally,
[tex:
|a+(-a)|
_
p
= lim
_
{
n->+
\infty
}
|(1+(p-1)
\sum
_
{
k=0
}
^
n
p
^
k
)|
_
p
]
. However,
[tex:
1+(p-1)
\sum
_
{
k=0
}
^
n
p
^
k
= 1+(p-1)
\frac
{
1-p
^
{
n+1
}
}
{
1-p
}
= p
^
{
n+1
}
]
and |p^{n+1}|_p = p^{-n+1}. Therefore, |a+(-a)|_p = 0, which can only mean that a+(-a)=0.
>a+b=b+a
[tex:
a+b = (a
_
0
+b
_
0
) + p (a
_
1
+b
_
1
) + p
^
2
(a
_
2
+b
_
2
) + ... = (b
_
0
+a
_
0
) + p (b
_
1
+a
_
1
) + p
^
2
(b
_
2
+a
_
2
) + ...
]
Multiplications look like much more of a pain though
Referenced by:
P47555
P48157
P50061
P50094
P47552
Wed 2023-06-07 19:28:52
link
reply
Dammit, I've been sniped!
P47555
Wed 2023-06-07 20:50:15
link
reply
P47550
Yeah, most of them do follow in some way from the corresponding properties holding on the digits.
One subtlety that it looks like you're ignoring sometimes in the proofs above are the carries. For example, instead of having
>
[tex:
((b
_
1
+c
_
1
) * a
_
m
+ (b
_
2
+ c
_
2
) * a
_
{
m-1
}
.. + (b
_
m
+c
_
m
) * a
_
1
) * n
^
{
m-1
}
]
as a digit in the result of a*(b+c), each of the
[tex:
(b
_
i
+c
_
i
)
]
would have a carry added to it and then the remainder would be taken modulo n, and also the whole thing would have a carry added to it and the remainder taken modulo n. So a little bit of work is required to show that those carries don't break anything.
The carries are not an issue for
>a+0=a
>most of the proof of a+(-a)=0
>a+b=b+a
but have to be accounted for in the more complicated theorems, mainly ones where you have multiple operations taking place like the distributive or associative properties.
A smaller issue is that your proof of a+(-a)=0 assumes associativity of addition, which you haven't proven yet.
P47551
>How come their are no other measures of distance with "good properties" than the three he described? (the usual absolute value, the p-adic and the one where L(0)=0 and L(x≠0)=k>0)
I don't know, but that would be another interesting thing to try proving.
>In the tri-force looking representation, are the holes the irrational numbers?
No, none of the numbers are in the interior of the triangular holes.
The same comment about the carries applies to your proof of (a+b)+c=a+(b+c).
>We can see that this will simplify to ...0000, but this doesn't convince me still.
The way I'm thinking about this is that we can start by treating these objects as simply infinite sequences of digits that are manipulated according to certain rules. It's a constructive approach rather than an axiomatic approach. The digit sequences and the algorithms on the digit sequences give us an explicit model of these numbers which we can prove satisfy the properties of a ring. Later on, we can show that the infinite digit sequence can be understood as an infinite sum, meaning the epsilon-N limit of a sequence of partial sums, and in fact the video has given the definition of absolute value that we'll need to define this limit appropriately. But we can't just interpret them as limits from the beginning, unless we assume some completeness axioms saying those limits exist. (We can, on the other hand,
[spoiler:
construct an alternate model of the n-adic integers as quotients of sequences which ought to have the same limit, then prove this model isomorphic to the "sequences of digits" model.
]
I suspect this approach will make the task easier, but I haven't gotten through all the proofs myself yet.)
In the constructive approach, it's pretty easy to see that when we add ...999 + 1, we're going to get ...000. It just follows from the algorithm.
Referenced by:
P50096
P47623
Fri 2023-06-09 03:49:47
link
reply
It is important to include the carrying, because if we ignore the carrying, we're not really proving stuff about n-adic integers; we're proving things about polynomial series with natural coefficients. It may be possible to carry some of these results over, but it does require an argument for how that works.
Referenced by:
P48384
P47634
Fri 2023-06-09 06:39:44
link
reply
too autistic; didnt read
Referenced by:
P47649
P47649
Fri 2023-06-09 09:02:51
link
reply
nadic_def.lean
4.90 KiB
P47634
If you think that's autistic, I just wrote out the algorithms in Lean.
Proving the ring properties will come later.
Referenced by:
P48070
P49893
P48070
Mon 2023-06-12 20:54:12
link
reply
plan.lean
12.5 KiB
P47649
>Proving the ring properties will come later.
Alright, I've got it all planned out in words.
Proof plan:
[spoiler:
We can convert any n-adic integer into the sequence of natural numbers obtained
by truncating the n-adic to 0,1,2,3,... digits. This conversion is reversible,
so if two n-adic integers produce the same sequence of truncations, they must
be equal. The effect of carrying on the length-k truncations is to take
the remainder mod nᵏ. From the algorithms given, we can confirm that adding,
multiplying, and negating n-adic integers adds, multiplies, and negates,
respectively, their length-k truncations mod nᵏ. Furthermore the length-k
truncations of 0 and 1 are equal to (0 mod nᵏ) and (1 mod nᵏ), respectively.
The ring properties then follow from the corresponding properties in
arithmetic mod nᵏ.
]
Further details are in the file. They should be enough to convince a human; next up is convincing the machine. First off, I'll need to find out what theorems mathlib has in its database, so I can potentially avoid having to prove a bunch of basic facts, like the fact that multiplication distributes over finite sums. (I think mathlib has a model of p-adics already, but of course we're not going to be using that.)
Referenced by:
P49946
P48088
Tue 2023-06-13 06:34:24
link
reply
6cdefa5b55968442e4788defb7393097b8a6b9d1ca26307cd4d0bf378e981a9f.jpg
132 KiB 1280x720
>How come their are no other measures of distance with "good properties" than the three he described? (the usual absolute value, the p-adic and the one where L(0)=0 and L(x≠0)=k>0)
I wish he specified what he means by "≅" here. Absolute values that give rise to the same topology, perhaps? There are definitely things like
[tex:
|
\cdot
|
_
p
^
k
]
that satisfy those properties but aren't the exact same function as something on the list.
Referenced by:
P48157
P48160
P49915
P50281
P48157
Tue 2023-06-13 19:33:21
link
reply
P47551
P48088
Some progress: I can show that if ||2|| = 1/2, then for all odd numbers n, ||n|| = 1.
First of all, it's easy to show that ||0|| = 0 and ||1|| = ||-1|| = 1.
First, ||0|| = 0 follows trivially from ||x|| = 0 iff x = 0.
Since
[tex:
||1||
\cdot
||1|| = ||1||
]
, the value of ||1|| must be either 0 or 1. It being 0 contradicts ||x|| = 0 iff x = 0, so it is 1.
Then we have
[tex:
||-1||
\cdot
||-1|| = ||1|| = 1
]
, so ||-1|| must be -1 or 1. We require
[tex:
||-1||
\geq
0
]
, so ||-1|| = 1.
Assume ||2|| = 1/2, and let n be an odd number. Then it can be written in the form
[tex:
n = a 2
^
k
+ 1
]
with k = 1. If any number m can be written as
[tex:
m = b 2
^
k
+ 1
]
with
[tex:
k
\geq
1
]
, then we can square it to obtain
[tex:
m
^
2
= (b
^
2
2
^
{
k-1
}
+ b) 2
^
{
k+1
}
+ 1
]
. Thus by repeatedly squaring n, we can obtain a number of the form
[tex:
n
^
{
(2
^
k
)
}
= c
_
k
2
^
{
k+1
}
+ 1
]
for arbitrarily large k.
From the triangle inequality we can obtain
[tex:
||a|| - ||b - a||
\leq
||b||
\leq
||a|| + ||b - a||
]
and
[tex:
||
\sum
_
{
i=0
}
^
n
a
_
i
||
\leq
\sum
_
{
i=0
}
^
n
||a
_
i
||
]
.
We can use this to put a constraint on ||n||. Decompose
[tex:
c
_
k
]
into its digits:
[tex:
c
_
k
=
\sum
_
{
i=0
}
^
{
u
_
k
}
c
_
{
ki
}
2
^
i
]
Then
[tex:
n
^
{
(2
^
k
)
}
- 1 =
\sum
_
{
i=0
}
^
{
u
_
k
}
c
_
{
ki
}
2
^
{
k+1+i
}
]
and
[tex:
||n
^
{
(2
^
k
)
}
- 1||
\leq
\sum
_
{
i=0
}
^
{
u
_
k
}
||c
_
{
ki
}
|| (1/2)
^
{
k+1+i
}
< (1/2)
^
k
]
so
[tex:
1 - (1/2)
^
k
< ||n||
^
{
(2
^
k
)
}
< 1 + (1/2)
^
k
]
.
Since squaring a positive number takes it further away from 1, we have
[tex:
1 - (1/2)
^
k
< ||n|| < 1 + (1/2)
^
k
]
for all k and therefore
||n|| = 1.
Referenced by:
P48160
P48160
Tue 2023-06-13 21:04:07
link
reply
P48157
Also this is enough to fix the absolute values for all rational numbers, because any rational number can be written in the form
[tex:
\frac
{
p
}
{
q
}
2
^
n
]
where n is an integer and p and q are odd integers.
Also the argument still follows if we set ||2|| to any value between 0 and 1, and we get a slightly different absolute value function which obeys all the constraints in
P48088
. But all of these absolute values would give us the same topology.
Then we can generalize this from 2 to an arbitrary prime p. First we use Fermat's little theorem to obtain
[tex:
n
^
{
(n-1) mod p
}
= a p + 1
]
for n not divisible by p. Then instead of repeatedly squaring, we repeatedly raise the number to the power of p.
And if any integer ||n|| has a value between 0 and 1, then one of its prime factors must have a value between 0 and 1. (We don't need to consider -1, 0, or 1 since we know their absolute values already.)
So at the moment I can show that either
> our absolute value function is equivalent to some p-adic absolute value function
or
> every nonzero integer has an absolute value
[tex:
\geq
1
]
.
Referenced by:
P50140
P48384
Fri 2023-06-16 13:54:01
link
reply
P47623
>It is important to include the carrying, because if we ignore the carrying, we're not really proving stuff about n-adic integers; we're proving things about polynomial series with natural coefficients.
Thought of a possibly even easier way to handle the carrying. Start by proving that power series with integer coefficients form a ring. Then let a ≅ b if x - n divides a(x) - b(x); this is an equivalence relation, and it's easy to show that addition and multiplication respect it. Then show that carry(a) = carry(b) if and only if a ≅ b.
In other works, the n-adic integers are the quotient ring obtained from the ring of power series with integer coefficients by quotienting out the ideal generated by x - n.
Mod Controls:
x
Reason: