Math Question

[Surlethe]

I'm having a hangup about Lagrange's theorem ([p prime and f(x) = \sum_i=0,^n{a_i*x^i} is a polynomial degree n ≥ 1, integral coefficients, a_n !≡ 0 (mod p)] → [f(x) ≡ 0 (mod p) has at most n incongruent solutions modulo p]; as an example, my book gives:

x^5 - 5x^3 + 4x ≡ 0 (mod p),

and states the congruence equation "obviously has at most p solutions modulo p". I'm having trouble seeing why it can have at most p solutions modulo p. An explanation would be quite appreciated.

[Kuroneko]

You are taking the modulus of the solutions. There are at most p solutions mod p because the group Z_p has exactly p members. Recall that a≡b mod n iff n|(a-b). If one takes the nonnegative remainders A and B of of a/n and b/n, respectively, then a≡b mod n iff A = B. Note that there are exactly p possible remainders when dividing by p; explicitly, Z_p = {0,1,2,...,p-1}. In this particular case, there are at most min{5,p} solutions: x^5-5x^3+4x ≡ 0 (mod p), so x(x-1)(x+1)(x-2)(x+2) ≡ 0 (mod p), and therefore the solution equivalence classes are {0,1,2,p-2,p-1}.

[Surlethe]

So the solutions x to that particular equation will have to be distinct elements of Z_p, and since |Z_p| = p, there can be at most p solutions. Thank you!

[Surlethe]

And another point I don't understand.

The proof of Hensel's Lemma starts with the following statement:

Since x = s is a solution to the equation f(x) ≡ 0 (mod p^a), any solution to f(x) ≡ 0 (mod p^(a+1)) must be of the form x = s + t*p^a.

I don't see why this is generally true; p^(a+1) doesn't divide into s + t*p^a, so any power of s + t*p^a isn't necessarily going to be congruent to 0 (mod p^(a+1)), right? What am I missing?

[Kuroneko]

Since x = s is a solution to the equation f(x) ≡ 0 (mod p^a), any solution to f(x) ≡ 0 (mod p^(a+1)) must be of the form x = s + t*p^a. I don't see why this is generally true; p^(a+1) doesn't divide into s + t*p^a, so any power of s + t*p^a isn't necessarily going to be congruent to 0 (mod p^(a+1)), right? What am I missing?

Are you certain that is the exact statement? My intuition says it is false, although I don't have the time right now to make sure. If one modifies "any solution to ... must be in the form" to "there is a solution to ... in the form," however, the claim is very easy to prove. I assume that f(x) is a polynomial with integer coefficients. Since (s+tp^a)^n ≡ s^n + ns^{n-1}tp^a (mod p^{a+1}), it follows that f(s+tp^a) ≡ f(s) + tp^a f'(s) (mod p^{a+1)). If p does not divide f'(s) and f(s) = Ap^a, then f'(s) has some multiplicative inverse F. Put t = -AF, and you have generated as solution to f(x) ≡ 0 (mod p^{a+1} from a solution to f(x) ≡ 0 (mod p^{a+1}); the case of p|f'(s) is trivial.

[Surlethe]

Are you certain that is the exact statement? My intuition says it is false, although I don't have the time right now to make sure.

From the book:

"Since x = s is a solution to (2.13) [that's Hensel's Lemma], any solution to f(x) ≡ 0 (mod p^(a+1)) must be of the form x = s + t*p^a for some t."

If one modifies "any solution to ... must be in the form" to "there is a solution to ... in the form," however, the claim is very easy to prove. I assume that f(x) is a polynomial with integer coefficients. Since (s+tp^a)^n ≡ s^n + ns^{n-1}tp^a (mod p^{a+1}), it follows that f(s+tp^a) ≡ f(s) + tp^a f'(s) (mod p^{a+1)). If p does not divide f'(s) and f(s) = Ap^a, then f'(s) has some multiplicative inverse F. Put t = -AF, and you have generated as solution to f(x) ≡ 0 (mod p^{a+1} from a solution to f(x) ≡ 0 (mod p^{a+1}); the case of p|f'(s) is trivial.

OK; I think I follow. You're starting with (s+tp^a)^n and running with it to see if you can get 0 (mod p^(a+1)) out of it.

Math is fun!

[Kuroneko]

"Since x = s is a solution to (2.13) [that's Hensel's Lemma], any solution to f(x) ≡ 0 (mod p^(a+1)) must be of the form x = s + t*p^a for some t."

Ach. There is an inherent ambiguity in this language, assuming (2.13) is f(x) ≡ 0 (mod p^a) [that's not Hensel's lemma by itself, but it is what you used prior], It can be interpreted as saying that if one picks a particular solution to f(s) ≡ 0 (mod p^a), then any solution x with f(x) ≡ 0 (mod p^{a+1}) can be written as x=s+tp^a. That's patently absurd. Fortunately, that's not the intended meaning, which is the correspondence between the solutions (note that t is unique mod p^{a+1} as long as p does not divide f'(s)).

OK; I think I follow. You're starting with (s+tp^a)^n and running with it to see if you can get 0 (mod p^(a+1)) out of it. Math is fun!

Right. The first congruence (s+tp^a)^n ≡ s^n + ns^{n-1}tp^a (mod p^{a+1}) follows directly from the binomial theorem, although it can by bypassed by the use of Taylor's theorem to assert f(s+tp^a) ≡ f(s) + tp^a f'(s) (mod p^{a+1)) directly.

[Surlethe]

"Since x = s is a solution to (2.13) [that's Hensel's Lemma], any solution to f(x) ≡ 0 (mod p^(a+1)) must be of the form x = s + t*p^a for some t."

Ach. There is an inherent ambiguity in this language, assuming (2.13) is f(x) ≡ 0 (mod p^a) [that's not Hensel's lemma by itself, but it is what you used prior],

Right. My mistake; that's part of the hypothesis for Hensel's Lemma.

It can be interpreted as saying that if one picks a particular solution to f(s) ≡ 0 (mod p^a), then any solution x with f(x) ≡ 0 (mod p^{a+1}) can be written as x=s+tp^a. That's patently absurd. Fortunately, that's not the intended meaning, which is the correspondence between the solutions (note that t is unique mod p^{a+1} as long as p does not divide f'(s)).

So the intended meaning is a "for every ... there exists" statement?

OK; I think I follow. You're starting with (s+tp^a)^n and running with it to see if you can get 0 (mod p^(a+1)) out of it. Math is fun!

Right. The first congruence (s+tp^a)^n ≡ s^n + ns^{n-1}tp^a (mod p^{a+1}) follows directly from the binomial theorem, although it can by bypassed by the use of Taylor's theorem to assert f(s+tp^a) ≡ f(s) + tp^a f'(s) (mod p^{a+1)) directly.

They used Taylor's theorem in the book as a lemma to prove Hensel's.

[Kuroneko]

So the intended meaning is a "for every ... there exists" statement?

That would certainly make a correct statement, but I suspect that the author attempted to say a solution for f(x) ≡ 0 (mod p^{a+1}) can always be put in the form x = s+tp^a for some s with f(s) ≡ 0 (mod p^a). The implicature of the author's statement, however, is that this is the case for an arbitrary but particular s. The former would have been completely correct. As above, f(s+tp^a) ≡ f(s) + tp^a f'(s) (mod p^{a+1)). Every x can be written as s+tp^a for some s, t. Assuming f(s+tp^a) ≡ 0 (mod p^{a+1}), we have f(s) + tp^a f'(s) = Ap^{a+1} for some A, and thus f(s) ≡ 0 (mod p^a). Therefore, a solution for f(x) ≡ 0 (mod p^{a+1}) can always be put in the form x = s+tp^a for some s with f(s) ≡ 0 (mod p^a).

They used Taylor's theorem in the book as a lemma to prove Hensel's.

That's quite natural, although there really isn't that much difference. According to the binomial theorem, (s+x)^n = s^n + ns^{n-1}x + n(n-1)/2 s^{n-2}x² + ... + C(n,k)s^{n-k}x^k + ... + x^n; this can be summed over all the powers of a given polynomial f(x) to give f(s+x) = f(s) + f'(x)x + f"(x)x² + ... + f^{(k)}(x) x^k/k! + ..., which is precisely Taylor's theorem.

[Surlethe]

I'm still messing around with the arithmetic function f(n) = the smallest m s.t. k(k+m) = n. The graph is ... interesting. Is there any particular reason the seem to be distributed linearly?

[Kuroneko]

I'm still messing around with the arithmetic function f(n) = the smallest m s.t. k(k+m) = n. The graph is ... interesting. Is there any particular reason the seem to be distributed linearly?

Well, a good polynomial fit should stay between y = 0 and y = x-1; for large data sets, this is rather difficult for high-degree polynomials except when the coefficients of powers greater than 1 are very small. If they're small, however, the polynomial is essentially linear over the domain. Thus, quadratic or above polynomials will not give signficant improvement over a linear fit.

[Surlethe]

I'm still messing around with the arithmetic function f(n) = the smallest m s.t. k(k+m) = n. The graph is ... interesting. Is there any particular reason the seem to be distributed linearly?

Well, a good polynomial fit should stay between y = 0 and y = x-1; for large data sets, this is rather difficult for high-degree polynomials except when the coefficients of powers greater than 1 are very small. If they're small, however, the polynomial is essentially linear over the domain. Thus, quadratic or above polynomials will not give signficant improvement over a linear fit.

I didn't word my question precisely. There appear to be different classes which graph exactly on a series of lines of the form y = x/n - n. Primes map to n=1 for obvious reasons; however, the others seem hardly transparent; for example:

{p|p prime} map to y - x = -1
{4,6,8,10,14,22,26,34,38,...} map to y - x/2 = -2
{9,12,15,18,21,27,33,39,...} map to y - x/3 = -3
etc.

If I get a chance, I'll scan the graph. It speaks volumes for itself.

[Kuroneko]

If x = n(n+f(x)), then of course f(x) = x/n-n.

[Surlethe]

If x = n(n+f(x)), then of course f(x) = x/n-n.

...

You take all the fun out of not knowing.


I'm also not seeing why it seems all the integral values of the graph of l(x) = p - x/p on the restricted range [p-1,0] are a subset of the graph of f(n). Is it equally simple?

[Kuroneko]

You take all the fun out of not knowing. :P

Ah, sorry; it just seemed too easy. Besides, you still haven't done \sum_{f(x)=1}{1/x}.

I'm also not seeing why it seems all the integral values of the graph of l(x) = p - x/p on the restricted range [p-1,0] are a subset of the graph of f(n). Is it equally simple?

Do you mean L_p:[p,p²]→[0,p-1] defined by L_p(x) = p - x/p? Your range is reversed. Your conjecture is false. Try to show why.

[Surlethe]

Ah, sorry; it just seemed too easy. Besides, you still haven't done \sum_{f(x)=1}{1/x}.

Hmm. A bit of research shows ζ(n) = ∫_1 . . . ∫_n [ ∏(dx_i, 1, n)/(1-∏(x_i, 1, n)), 0, 1]. So ζ(1) diverges because ζ(1) = ∫[dx/(1-x), 0, 1].

Is that right?

[Kuroneko]

Hmm. A bit of research shows ζ(n) = ∫_1 . . . ∫_n [ ∏(dx_i, 1, n)/(1-∏(x_i, 1, n)), 0, 1]. So ζ(1) diverges because ζ(1) = ∫[dx/(1-x), 0, 1]. Is that right?

That's true. In general, ζ(s) = \sum_{k>0}{1/k^s} for Re(s)≥1, so ζ(1) is the harmonic series. But if f(n) is the smallest m s.t. n = k(k+m) (n positive integer), S = \sum_{f(n)=1}{1/n} is definitely not the harmonic series, since the numbers n for which f(n) = 1 are generated by a quadratic. In fact, S < ζ(2) = \sum_{f(n)=0}{1/n}.

[Surlethe]

Hmm. A bit of research shows ζ(n) = ∫_1 . . . ∫_n [ ∏(dx_i, 1, n)/(1-∏(x_i, 1, n)), 0, 1]. So ζ(1) diverges because ζ(1) = ∫[dx/(1-x), 0, 1]. Is that right?

That's true. In general, ζ(s) = \sum_{k>0}{1/k^s} for Re(s)≥1, so ζ(1) is the harmonic series. But if f(n) is the smallest m s.t. n = k(k+m) (n positive integer), S = \sum_{f(n)=1}{1/n} is definitely not the harmonic series, since the numbers n for which f(n) = 1 are generated by a quadratic. In fact, S < ζ(2) = \sum_{f(n)=0}{1/n}.

My mistake; for some reason I misread f(x) = 1 as x = 1.

\sum_{f(n)=1}{1/n} will be the sum of the x-values of the intersection x = 1 with the lines y = x/n - n, since it's not until x = 3 that lines start having gaps. Geometrically, it appears the values will start with two and increase in jumps of even numbers, so summing the numbers themselves is just summing twice the triangular numbers -- i.e., 2 (1 + 3 + 6 + 10 + ...). Inverting, this gives \sum_{n is triangular}{1/n}/2. The formula for the kth triangular number is k(k+1)/2, so the inverse of the kth triangular number will be 2/k(k+1). The two cancels with 1/2, leaving \sum_{n=1}{1/n(n+1)} -- which we already knew.

As n grows, 1/n(n+1) asymptotically approaches (1/n)^2. So lim_{n→∞}{\sum{1/n(n+1)} = ζ(2)?



I wonder what a 3d graph looks like, where the z-axis is the ith number in the sequence of each image.

[Kuroneko]

... leaving \sum_{n=1}{1/n(n+1)} -- which we already knew.

Well, it was an interesting way to arrive at it, but yes, that's the sum.

As n grows, 1/n(n+1) asymptotically approaches (1/n)^2. So lim_{n→∞}{\sum{1/n(n+1)} = ζ(2)?

No. Asymptotic convergence of the terms won't compensate for the differences between the partial sums. Trust me on this--you won't have to involve the zeta funtion at all to find this sum.

[Surlethe]

No. Asymptotic convergence of the terms won't compensate for the differences between the partial sums.

I caught that in the middle of my R:TW battle after I posted.

Trust me on this--you won't have to involve the zeta funtion at all to find this sum.

Okay; the gamma function?

Seriously, though: I'm a bit too tired to think straight at the moment, so I'm just messing around with the idea of taking \sum_{n=1}{1/n(n+1) - 1/n^2}. Would doing so mitigate the difference in the partial sums?

[Kuroneko]

Okay; the gamma function? :P

Nothing so complicated, I assure you.

Seriously, though: I'm a bit too tired to think straight at the moment, so I'm just messing around with the idea of taking \sum_{n=1}{1/n(n+1) - 1/n^2}. Would doing so mitigate the difference in the partial sums?

Eh, ζ(2) won't help you at all; however, if you drop the power of two above and investigate the partial sums, you might get somewhere. Or maybe not.

[Surlethe]

This question is completely irrelevant to the previous context of the thread (don't get worried, though; I'm still working on the partial sums), but this is a math question thread, so there you go:

Doesn't the least upper bound axiom follow from the well-ordering principle?

[Kuroneko]

Doesn't the least upper bound axiom follow from the well-ordering principle?

No. The well-ordering principle refers to the natural numbers only. If you're confusing it with the axiom of choice (the axiom that any set can be well-ordered), that doesn't follow either--lub axiom (aka "axiom of completeness" aka "axiom of supremum"), then it may depend on how real numbers are defined. Thing is, the presense of a lub for any set of reals bounded above is really a theorem rather than an axiom if one takes care to actually define the real numbers in terms of simpler structures rather than simply posit the field axioms. Two of the most common ways of doing so are using Dedekind cuts of the rationals or Cauchy sequences of rationals. Let ℚ denote the rationals.
Def (1): a set α⊂ℚ is a cut iff α≠ℚ, α is nonempty, α does not contain a largest rational, and for every p∈α and rational q<p, q∈α. Arithmetic can be defined on them (with some speicic cases to take care of negatives), and α<β iff there is a p∈β greater than all q∈α. A set of cuts bounded above by another cut will have a least upper bound, which happens to be the union of all the cuts in that set. One may then call cuts on rationals "real numbers." This is independent of the axiom of choice.
Def (2): a sequence (a_k) is Cauchy iff for all ε>0 there is a natural number N such that for all n>N and m>N |a_n-a_m|<ε. Two of rationals are equal if their difference converges to 0. However, I don't think there is any way to prove the lub theorem without the axiom of choice to pick out an appropropriate sequence of rationals from a given set of Cauchy sequences. As above, one may call equivalence classes of such Cauchy sequences on rationals "real numbers."

[Surlethe]

Ahah! I made a connection: the sequence of partial sums of \sum_{n=1}{1/n(n+1)} is the sequence of inverted tetragonal numbers.

The reason this bothers me is I tried for a week several months ago to come up with a closed formula for the nth tetragonal number.

[Kuroneko]

Ahah! I made a connection: the sequence of partial sums of \sum_{n=1}{1/n(n+1)} is the sequence of inverted tetragonal numbers. The reason this bothers me is I tried for a week several months ago to come up with a closed formula for the nth tetragonal number. :?

If you mean that the summation is of the recipricol triangular numbers (times a constant), then yes. How do you define tetragonal numbers? The sequence of partial sums a_n = \sum_{k=1}^n{1/k(k+1)} definitely does not tend to zero.