Challenge Can You Solve These Math Challenges?

[nuuskur]

The expression $a\equiv b\pmod{n}$ is equivalent to $n\mid (a-b)$. I will be working with the latter.

As previous attempts had failed, it's time for some good ol' induction.

Spoiler: Problem 2

Proof by induction on $n$.
Let $a=:2k+1$ be an arbitrary odd number. For $n=1$ it holds that
<br /> 8\mid (2k+1)^2 -1 \quad\mbox{i.e}\quad 8\mid 4k(k+1)\qquad (k\in\mathbb Z)<br />
Indeed, if $8\mid 4k(k+1)$, then $8\mid \left (4k(k+1) + 8(k+1) \right )$ i.e $8\mid 4(k+1)(k+2)$.Suppose for some $n>1$ it holds that $2^{n+1} \mid (2k+1)^{2^{n-1}}-1, k\in\mathbb Z$. We need to show
<br /> 2^{n+2} \mid (2k+1)^{2^{n}}-1,\quad k\in\mathbb Z<br />
We have
<br /> (2k+1)^{2^{n}}-1 = \left [(2k+1)^{2^{n-1}}\right ]^2 -1 = \left [(2k+1)^{2^{n-1}}-1\right ]\left [(2k+1)^{2^{n-1}}+1\right ]<br />
The quantity $2^{n+1}$ divides the left factor of the RHS by inductive assumption. The right factor of the RHS is even, therefore divisible by $2$. Therefore, for every $k\in\mathbb Z$ it holds that
<br /> 2^{n+2} \mid (2k+1)^{2^{n}}-1\qquad (n\in\mathbb N).<br />
(corrections suggested by @fresh_42 included)

Normally, I avoid induction like the plague. I use it as a last resort, since it often makes the result feel..cheap. It's some kind of silly superstition. (graph theoretic induction schemes are the work of the devil, but I digress...)

Spoiler: Previous idea

Sketch: proof by contrapositive. Assume $1\leq GCD(2^{n+2}, a^{2^n}-1) =:d <2^{n+2}$. Suffices to show the number $a$ is even. If $d=1$, the result follows immediately due to for some $u,v\in\mathbb Z$ the equality $u2^{n+2} + v\left (a^{2^n}-1\right )=1$ holds. If, however, $d$ is a power of $2$, I would instead get that $a^{2^n}$ is odd, therefore $a$ is odd.

Does anybody see a way to exclude $d>1$ ?

 

[fresh_42]

Well done, @nuuskur. I don't share your sentiments towards induction, the more as this proof well-nigh screams for an induction. I even met people, who would instantly call for an induction rather than to use anything with a negation. They would feel exact the opposite: Induction is algorithmic, constructive, and ergo good. Negation is a logical trick, and ergo evil.

Just to improve your writing, not to criticize your proof:

It suffices to show

That's misleading. As it is exactly what we have to prove, why is it "only" sufficient? Better would have been something like: "Thus we must show" or similar. "Sufficient" let's your readers search where you've restricted generality, but there is no such place.

The quantity $2^{n+1}$ divides the left term

factor on the RHS

by inductive assumption. The right term

factor

is even, therefore divisible by $2$.

A "left term" is sought on the left, not on the right side of an equation.

As said, not a big deal, but such small inaccuracies make it harder to read. E.g. while scratching your proof that I could better follow your steps, my induction assumption looked like: $a^{2^{n-1}}-1 =(2k+1)^{2^{n-1}} - 1 = 2^{n+1}\cdot N$ and I used this $N$ again in the last line to immediately see the divisibility: $a^{2^{n}}-1 = \ldots = (2^{n+1}\cdot N)\cdot (2\cdot M)$.
So with a little effort, I removed all steps which required to remember the steps in between (means to look up again and again: what was it here, n, n+1, n-1?).

I know, that is nitpicking and not really necessary to mention. I just wanted to demonstrate w.r.t. my previous criticism, how little helpers can make an entire proof easier to read.

 

[Adam Kohnle]

If you have specific questions, I mean those which Wiki doesn't answer (or PF hasn't already), feel free to ask, either here or if you're really interested in greater details, in a separate thread. The technical language often sounds like more than it actually is. The Manhattan metric, e.g. is nothing else as counting blocks instead of diagonals, and the French Railway metric means: all distances have to include Paris.

I appreciate that and if I have questions then I will ask y'all. For now I am going to worry about learning other things since I am beginning college and I still am not sure what my second major should be. I have to do one major as secondary education and then one major in the STEM field so I can teach STEM but I'm not sure which to pick. I might make a thread about it if it is allowed.

 

[fresh_42]

I appreciate that and if I have questions then I will ask y'all. For now I am going to worry about learning other things since I am beginning college and I still am not sure what my second major should be. I have to do one major as secondary education and then one major in the STEM field so I can teach STEM but I'm not sure which to pick. I might make a thread about it if it is allowed.

Sure, you're welcome. We have an extra forum for those kind of questions: Academic Guidance. Not all forums are read by all members, so to place a question in the right forum addresses the right people, here often current or former teachers and professors. And, of course, the better you pose your question, like telling what your major is, the better the answers are which you will receive.

 

[Adam Kohnle]

Sure, you're welcome. We have an extra forum for those kind of questions: Academic Guidance. Not all forums are read by all members, so to place a question in the right forum addresses the right people, here often current or former teachers and professors. And, of course, the better you pose your question, like telling what your major is, the better the answers are which you will receive.

Thanks so much! I will go and do that!

 

[QuantumQuest]

As previous attempts had failed, it's time for some good ol' induction.

@nuuskur you did well. Just try to be somewhat more straightforward and structured in your solutions and you'll be really fine. This is no kind of criticism or some negative comment; I just tell you for your own good.

 

[archaic]

A try at question 10.

Spoiler

Let x = ⌊n!e⌋
⟺ (property) n!e − 1 < x ≤ n!e
⟺ (multiply by -1) - n!e ≤ - x < 1 - n!e
⟺ (add n!e to both sides) 0 ≤ n!e - x < 1
$$\lim_{n\to\infty} 0 ≤ \lim_{n\to\infty} (n!e - \lfloor n!e \rfloor) ≤ \lim_{n\to\infty} 1$$ ?

 

[nuuskur]

@archaic
When you take the limit, strict inequalities become non-strict.

 

[archaic]

@archaic
When you take the limit, strict inequalities become non-strict.

Thank you

 

[nuuskur]

Number 5 seems like a fun exercise. I'll assume we already know these mappings are metrics.

Spoiler: Problem 5

French Metro. For every $a,b\in\mathbb R^2$
<br /> \rho (a,b) := \begin{cases} \lvert a-b\rvert, &amp;\exists k: ka=b \\ |a|+|b|, &amp;\mbox{otherwise}\end{cases}<br />
where $|a|$ denotes the Euclidean distance (from Paris). Describe the open ball $B((2,1),3)$.
If one observes $R(2,1)$ as a bound vector (on Paris), multiplying it by some number, we just stretch this vector so whenever $\rho (a,b) = |a-b|$, they are situated on the straight line determined by Paris and Reims. Then we have the condition $\rho (X,R)<3$ i.e
<br /> |(2k,k) - (2,1)| = |(2(k-1), k-1)| \overset{*}= |k-1||(2,1)| = |k-1|\sqrt{5}&lt;3<br />
(*) the mapping $|\cdot|$ is actually a norm, so I can use its homogeneity property
therefore $-\frac{3}{\sqrt{5}} +1 < k < \frac{3}{\sqrt{5}} +1$.
On the other hand, if $X$ does not lie on the line, the minimum distance between Reims and $X$ is at least the distance between Paris and Reims. (Even if the other city is like 5 km north, you have to take the train back to Paris and only then get to your destination, unless you don't mind walking )
More specifically we have $\rho (X,R)<3$ i.e
<br /> |(x,y)| + |(2,1)| = \sqrt{x^2 + y^2} + \sqrt{5} &lt; 3 \implies x^2+y^2 &lt; \left (3-\sqrt{5}\right )^2<br />
It's a circle around Paris with radius $3-\sqrt{5}$, boundary excluded.
The open ball consists of the segment with specified $k$ and the circle. (think lollipop)
---------------------------------------------------------------------------------------------------------------------------
Manhattan metric. For every $(a,b),(c,d)\in\mathbb R^2$
<br /> \rho ((a,b),(c,d)) := |a-c| + |b-d|.<br />
Suppose $\rho ((x,y),(2,1))<3$ i.e
<br /> |x-2| + |y-1| &lt;3<br />
Since we are adding two non-negative quantities they are both bounded by $3$. This means $-1<x<5$ or $-2<y<4$. (so the open ball definitely lives inside of this open rectangle)

Firstly, suppose $y\geq 1$. We have the condition $|x-2| <3 - (y-1) = 4-y$.

1. If $x\geq 2$, then $x+y<6$ (strictly under the line $y = -x+6$)
2. If $x<2$, then $y-x<2$ (strictly under the line $y=x+2$)

Secondly, suppose $y<1$. We have the condition $|x-2| < 3 +y-1 = y+2$.

1. If $x\geq 2$, then $x-y<4$ (strictly above the line $y=x-4$)
2. If $x<2$, then $x+y>0$ (strictly above the line $y=-x$).

Edit: the shape is a special case of a parallelogram with vertices lying on the intersections of the lines. The vertices are $(-1,1), (2,4), (5,1), (2,-2)$. The boundary is excluded.
---------------------------------------------------------------------------------------------------------------------------
Maximum metric. For every $(a,b),(c,d)\in\mathbb R^2$
<br /> \rho ((a,b),(c,d)) := \max \lbrace |a-c|, |b-d|\rbrace<br />
So, suppose $\rho ((x,y),(2,1))<3$ i.e
<br /> \max \lbrace |x-2|, |y-1|\rbrace &lt; 3<br />
This is the rectangle I was talking about in Manhattan exercise: $-1<x<5$ or $-2<y<4$

Edit: It's a square, sorry. With vertices $(-1,4), (5,4), (5,-2), (-1,-2)$. The boundary is excluded.

The balls in general metric spaces exhibit some very "unball"-like characteristics

 

[fresh_42]

The balls in general metric spaces exhibit some very "unball"-like characteristics

That's been the idea behind the question: a different metric is a different way of measuring, not just a different scale like meter and yards.

In the French Railway metric, we can easily travel to Luxembourg but won't reach - and that is the good news - Saint Quentin, although it is "closer" (in the ordinary sense). The ball is shaped like a hammer in a hammer throw competition: a rope of some fixed length and everything inside the Paris highway circle.
Your description and numbers are correct.

For the other two metrics, where a ball is shaped like a rectangular, can you tell the name of the shapes and their vertices?

 

[nuuskur]

For the other two metrics, where a ball is shaped like a rectangular, can you tell the name of the shapes and their vertices?

I've edited #40 with this information.

 

[fresh_42]

I've edited #40 with this information.

Thanks. Btw. the "ball" in the Manhattan metric is called a rhombus, a square standing on one of its corners. Here's a quick illustration:

 

[lpetrich]

I'll do Problem 10.

Spoiler

For that, we must start with the series
$$e = \sum_{k=0}^\infty \frac{1}{k!}$$
Multiply by n!:
$$n! e = \sum_{k=0}^\infty \frac{n!}{k!}$$
Split the series in two, after k = n: $n! e = e_1 + e_2$ where
$$ e_1 = \sum_{k=0}^n \frac{n!}{k!} ,\ e_2 = \sum_{k=n+1}^\infty \frac{n!}{k!} = \sum_{k=1}^\infty \frac{n!}{(n+k)!} $$
with k redefined for e₂.

For e₁, each of the terms is (k+1)*(k+2)*...*n, and is thus an integer. Therefore, e₁ is an integer.

For e₂, however, each of the terms is the reciprocal of (n+1)*(n+2)*...*(n+k), and each part of that term has lower limit n+1. That reciprocal thus has the lower limit (n+1)^k. Thus,
$$ e_2 = \sum_{k=1}^\infty \frac{1}{(n+1)(n+2) \cdots (n+k)} < \sum_{k=1}^\infty \frac{1}{(n+1)^k} = 1/n $$
using the familiar formula for the sum of a geometric series.

This means that e₂ is always between 0 and 1/n for n >= 1, and thus that it is always between 0 and 1. That means that (n!*e) has integer part e₁ and fractional part e₂ for n >= 1. Thus, $n!e - \lfloor n!e \rfloor = e_2$

Though e₂ is positive, it can be made arbitrarily small with some suitable selection of n, and thus $\lim_{n\to\infty} e_2 = 0$. Thus proving that
$$\lim_{n\to\infty}(n!e - \lfloor n!e \rfloor) = 0$$

 

[QuantumQuest]

A try at question 10.

I appreciate your efforts but can this way lead to any safe conclusion?Can you come up with some other way?

 

[QuantumQuest]

@lpetrich well done!

 

[lpetrich]

I'll try problem 9.

Spoiler

For a space with coordinates xⁱ, the one-form $\omega = \omega_i dx^i$, assuming summation over dummy indices like i here. Integrating over curve C with parameter t, with $x^i = x^i(t)$,
$$\int_C \omega = \int_C \omega_i \frac{dx^i}{dt} dt$$
Using Mathematica to do the mathematical grunt work, I find that this problem's integral has the value 5.

The exterior derivative of ω is
$$\nu = d\omega = \frac12 \left( \frac{d\omega_j}{dx^i} - \frac{d\omega_i}{dx^j}\right) dx^i \wedge dx^j$$
where the wedge denotes antisymmetry. For this problem, $\nu = z dx \wedge dz$.

Taking a further exterior derivative, I find $d\nu = dz \wedge dx \wedge dz = 0$, and ν is thus closed. This result can be proved more generally:

d(d(any n-form)) = 0

as a consequence of the antisymmetry of the exterior derivative.

 

[fresh_42]

I'll try problem 9.

Spoiler

For a space with coordinates xⁱ, the one-form $\omega = \omega_i dx^i$, assuming summation over dummy indices like i here. Integrating over curve C with parameter t, with $x^i = x^i(t)$,
$$\int_C \omega = \int_C \omega_i \frac{dx^i}{dt} dt$$
Using Mathematica to do the mathematical grunt work, I find that this problem's integral has the value 5.

The exterior derivative of ω is
$$\nu = d\omega = \frac12 \left( \frac{d\omega_j}{dx^i} - \frac{d\omega_i}{dx^j}\right) dx^i \wedge dx^j$$
where the wedge denotes antisymmetry. For this problem, $\nu = z dx \wedge dz$.

Taking a further exterior derivative, I find $d\nu = dz \wedge dx \wedge dz = 0$, and ν is thus closed. This result can be proved more generally:

d(d(any n-form)) = 0

as a consequence of the antisymmetry of the exterior derivative.

The results are correct, but I want to see the steps. E.g. there are only six steps to get 5 and only 4 to calculate $\nu$. Shouldn't be too many to write out.

 

[lpetrich]

Here are some evaluations.

Spoiler

For doing the integral, the integrand is
$$ z^2 \frac{dx}{dt} + 2y \frac{dy}{dt} + x z \frac{dz}{dt} = 1^2 \frac{d(t^2)}{dt} + 2(2t) \frac{d(2t)}{dt} + t^2 \cdot 1 \frac{d(1)}{dt} = 2t + 8t + 0 = 10t $$
Integrating it is easy: $\int (10 t) dt = 5 t^2$, and plugging in the limits of integration gives $5(1^2) - 5(0^2) = 5$.

For taking the derivative, I do
$$ d(z^2 (dx) + 2y (dy) + x z (dz)) = 2z (dz \wedge dx) + 2 (dy \wedge dy) + z (dx \wedge dz) + x (dz \wedge dz) = - 2z (dx \wedge dz) + z (dx \wedge dz) = z (dx \wedge dz) $$

 

[fresh_42]

Here are some evaluations.

Spoiler

For doing the integral, the integrand is
$$ z^2 \frac{dx}{dt} + 2y \frac{dy}{dt} + x z \frac{dz}{dt} = 1^2 \frac{d(t^2)}{dt} + 2(2t) \frac{d(2t)}{dt} + t^2 \cdot 1 \frac{d(1)}{dt} = 2t + 8t + 0 = 10t $$
Integrating it is easy: $\int (10 t) dt = 5 t^2$, and plugging in the limits of integration gives $5(1^2) - 5(0^2) = 5$.

For taking the derivative, I do
$$ d(z^2 (dx) + 2y (dy) + x z (dz)) = 2z (dz \wedge dx) + 2 (dy \wedge dy) + z (dx \wedge dz) + x (dz \wedge dz) = - 2z (dx \wedge dz) + z (dx \wedge dz) = z (dx \wedge dz) $$

Yes, and for sake of completeness, the initial steps are formally:
$$\int_{\Gamma} \omega = \int_{[0,1]} \gamma^*(\omega)=\int_{[0,1]} \omega(d\gamma)=\int_{[0,1]} (z^2 dx +2ydy+xzdz)d\gamma $$

 

[lpetrich]

I'll take on problem 1, though I'm only somewhat familiar with its subject matter.

Spoiler

(a) This is presumably for finding the primitive polynomials in GF8. These are cubic polynomials with coefficients in GF2 that cannot be expressed as products of corresponding polynomials for GF4 and GF2. I will use x as an undetermined variable here.

For GF2, the primitive polynomials are x + (0,1) = x, x+1.

For GF4, we consider primitive-polynomial candidates x² + (0,1)*x + (0,1): x², x² + 1 = (x + 1)², x² + x = x(x + 1), x² + x + 1. That last one is the only primitive polynomial for GF4.

For GF8, we consider primitive-polynomial candidates x³ + (0,1)*x² + (0,1)*x + (0,1): x³, x³ + 1 = (x² + x + 1)*(x + 1), x³ + x = x * (x + 1)², x³ + x + 1, x³ + x² = x² * (x + 1), x³ + x² + 1, x³ + x² + x = x*(x² + x + 1), x³ + x² + x + 1 = (x + 1)³.

Thus, GF8 has primitive polynomials x³ + x + 1 and x³ + x² + 1.

(b) There is a problem here. A basis is easy to define for addition: {1, x, x²} where multiplication uses the remainder from dividing by a primitive polynomial. The additive group is thus (Z2)³. The multiplicative group is, however, Z7, and it omits 0. That group has no nontrivial subgroups, so it's hard to identify a basis for it.

(c) That is a consequence of every finite field GF(pⁿ) being a subfield of an infinite number of finite fields GF(p^m*n), each one with a nonzero number of primitive polynomials with coefficients in GF(pⁿ). Since each field's primitive polynomials cannot be be factored into its subfields' ones, each field adds some polynomial roots, and thus, there are an infinite number of such roots.

I will now try to show that every finite field has a nonzero number of primitive polynomials with respect to some subfield. First, itself: for all elements a of F relative to F, (x - a) is primitive. Thus, F has N primitive polynomials. For GF(p^m*n) relative to GF(pⁿ), I will call the number N(m). One can count all the possible candidate polynomials for GF(p^m*n), and one gets
$$ \sum_{\sum_k k m_k = r} \prod_k P(N(k),m_k) = N^r $$
If N is a prime, then the solution is known:
$$ N(m) = \frac{1}{m} \sum_{d|m} N^{m/d} \mu(d) $$
where the μ is the Moebius mu function, (-1)^(number of distinct primes if square-free), and 0 otherwise. I don't know if that is correct for a power of a prime.

 

[fresh_42]

I'll take on problem 1, though I'm only somewhat familiar with its subject matter.

Spoiler

(a) This is presumably for finding the primitive polynomials in GF8. These are cubic polynomials with coefficients in GF2 that cannot be expressed as products of corresponding polynomials for GF4 and GF2. I will use x as an undetermined variable here.

For GF2, the primitive polynomials are x + (0,1) = x, x+1.

For GF4, we consider primitive-polynomial candidates x² + (0,1)*x + (0,1): x², x² + 1 = (x + 1)², x² + x = x(x + 1), x² + x + 1. That last one is the only primitive polynomial for GF4.

For GF8, we consider primitive-polynomial candidates x³ + (0,1)*x² + (0,1)*x + (0,1): x³, x³ + 1 = (x² + x + 1)*(x + 1), x³ + x = x * (x + 1)², x³ + x + 1, x³ + x² = x² * (x + 1), x³ + x² + 1, x³ + x² + x = x*(x² + x + 1), x³ + x² + x + 1 = (x + 1)³.

Thus, GF8 has primitive polynomials x³ + x + 1 and x³ + x² + 1.

(b) There is a problem here. A basis is easy to define for addition: {1, x, x²} where multiplication uses the remainder from dividing by a primitive polynomial. The additive group is thus (Z2)³. The multiplicative group is, however, Z7, and it omits 0. That group has no nontrivial subgroups, so it's hard to identify a basis for it.

(c) That is a consequence of every finite field GF(pⁿ) being a subfield of an infinite number of finite fields GF(p^m*n), each one with a nonzero number of primitive polynomials with coefficients in GF(pⁿ). Since each field's primitive polynomials cannot be be factored into its subfields' ones, each field adds some polynomial roots, and thus, there are an infinite number of such roots.

I will now try to show that every finite field has a nonzero number of primitive polynomials with respect to some subfield. First, itself: for all elements a of F relative to F, (x - a) is primitive. Thus, F has N primitive polynomials. For GF(p^m*n) relative to GF(pⁿ), I will call the number N(m). One can count all the possible candidate polynomials for GF(p^m*n), and one gets
$$ \sum_{\sum_k k m_k = r} \prod_k P(N(k),m_k) = N^r $$
If N is a prime, then the solution is known:
$$ N(m) = \frac{1}{m} \sum_{d|m} N^{m/d} \mu(d) $$
where the μ is the Moebius mu function, (-1)^(number of distinct primes if square-free), and 0 otherwise. I don't know if that is correct for a power of a prime.

Although your language is in part a bit unusual, the basic ideas are correct.
To finish what you've deduced for part a), we can write
$$
\mathbb{F}_8 \cong \mathbb{F}_2[x]/(x^3+x+1) \cong \mathbb{F}_2 / (x^3+x^2+1)
$$
Part c) is basically correct, although I haven't checked the formulas. But to consider $\mathbb{F}_{p^n}$ is the right idea. The argument can be simplified a lot. All these fields are algebraic over their prime field $\mathbb{F}_p$, so all of them have to be included in the algebraic closure $\mathbb{A}_p$. But with each new $n$ we get a larger field and all of them must be part of $\mathbb{A}_p$, and $n$ doesn't stop. If we want to "construct" $\mathbb{A}_p$, then it can be shown, that
$$
\mathbb{A}_p = \cup_{n \in \mathbb{N}} \mathbb{F}_{p^{n!}} \text{ with the chain } \mathbb{F}_{p^{1!}} < \mathbb{F}_{p^{2!}} < \ldots
$$
where the inclusions of subfields are strict.

As a hint for part b) - and this is the usual way to do it in all of these cases - simply define a number $\xi$ which satisfies $\xi^3+\xi +1=0$. It is the same thing which we do from $\mathbb{R} < \mathbb{C} \cong \mathbb{R}[x]/(x^2+1) \cong \mathbb{R}[ i ]$. We define a number $i$ which satisfies $i^2 + 1 = 0$. We simply call it $i$. Now try to express all elements of $\mathbb{F}_8$ in terms of $\mathbb{F}_2=\{0,1\}$ and $\xi$, i.e. $\mathbb{F}_8 = \mathbb{F}_2[\xi]\,.$

 

[archaic]

I appreciate your efforts but can this way lead to any safe conclusion?Can you come up with some other way?

Maybe for another challenge :p

 

[lpetrich]

I will now continue with Problem 1

Spoiler

About (b), one defines GF(8) in terms of GF(2) as polynomials (0 or 1)*x² + (0 or 1)*x + (0 or 1). One defines addition and multiplication in the usual way for polynomials, but for multiplication, one must divide by one of the primitive polynomials and take the remainder. Another way of interpreting this is to suppose that x is one of the roots of one of the primitive polynomials. Those primitive polynomials: x³ + x + 1 and x³ + x² + 1.

(c) I have an insight into the issue of how many primitive polynomials an extended field has relative to its original field. I had earlier found a formula for N(m), the number of primitive polynomials of a field that is polynomials up to degree m-1 in the original field: F' ~ (F)^m. In terms of the number N of elements of F,
$$ \sum_{\sum_k k m_k = n} \sum_k P(N(k),m_k) = N^n $$
where P is the Pochhammer symbol $P(a,m) = a(a+1)\cdots(a+m-1)/m!$.

This looks like a difficult equation to solve for the N(k)'s, but there is a nice trick for doing so. Multiply by sⁿ and add:
$$ \prod_k \left( \sum_m P(N(k),m) s^{km} \right) = \sum_n (Ns)^n $$
Use the negative-power generalization of the binomial theorem:
$$ \prod_k (1 - s^k)^{-N(k)} = (1 - Ns)^{-1} $$
Take the logarithm:
$$ - \sum_k N(k) \log (1 - s^k) = - \log (1 - Ns) $$
Expand in powers of s, using the familiar log(1+x) series:
$$ \sum_{m|n} \frac1m N(n/m) = \frac1n N^n $$
Instead of complicated nonlinear equations in the N(k)"s, we have linear equations in them. That should make it easier to solve for them.

 

[fresh_42]

I will now continue with Problem 1

Spoiler

About (b), one defines GF(8) in terms of GF(2) as polynomials (0 or 1)*x² + (0 or 1)*x + (0 or 1). One defines addition and multiplication in the usual way for polynomials, but for multiplication, one must divide by one of the primitive polynomials and take the remainder. Another way of interpreting this is to suppose that x is one of the roots of one of the primitive polynomials. Those primitive polynomials: x³ + x + 1 and x³ + x² + 1.

(c) I have an insight into the issue of how many primitive polynomials an extended field has relative to its original field. I had earlier found a formula for N(m), the number of primitive polynomials of a field that is polynomials up to degree m-1 in the original field: F' ~ (F)^m. In terms of the number N of elements of F,
$$ \sum_{\sum_k k m_k = n} \sum_k P(N(k),m_k) = N^n $$
where P is the Pochhammer symbol $P(a,m) = a(a+1)\cdots(a+m-1)/m!$.

This looks like a difficult equation to solve for the N(k)'s, but there is a nice trick for doing so. Multiply by sⁿ and add:
$$ \prod_k \left( \sum_m P(N(k),m) s^{km} \right) = \sum_n (Ns)^n $$
Use the negative-power generalization of the binomial theorem:
$$ \prod_k (1 - s^k)^{-N(k)} = (1 - Ns)^{-1} $$
Take the logarithm:
$$ - \sum_k N(k) \log (1 - s^k) = - \log (1 - Ns) $$
Expand in powers of s, using the familiar log(1+x) series:
$$ \sum_{m|n} \frac1m N(n/m) = \frac1n N^n $$
Instead of complicated nonlinear equations in the N(k)"s, we have linear equations in them. That should make it easier to solve for them.

Please call the polynomials irreducible, because that's what counts. A polynomial is primitive, if it's coefficients are all coprime, which doesn't make much sense over a field in general and especially over $\mathbb{F}_2$. There are primitive elements of a field extension, namely those who generates it, say $\xi$. In our example if we take the easier polynomial of the two, we have $\mathbb{F}_8=\mathbb{F}_2[\xi]$ with $\xi^3+\xi+1=0$. The polynomial $x^3+x+1$ is called minimal polynomial and it is irreducible over $\mathbb{F}_2$, i.e. it cannot be factored in $\mathbb{F}_2[x]$ which in this case automatically means it has no zeros in $\mathbb{F}_2$.

Now obviously $\xi \neq 0$, so $\mathbb{F}^*_8 = \mathbb{F}_8 - \{0\} \cong \mathbb{Z}_7 = \langle a\,\vert \,a^7=1 \rangle$ and we can chose $a=\xi$. From there you can directly calculate all $\xi^n$ in terms of a linear $\mathbb{F}_2-$basis of $\mathbb{F}_8$ given by $\{1,\xi,\xi^2\}$. These seven vectors are what is asked for, because with them, we can see all addition and multiplication rules without having to to fill in complete tables.

 

[StoneTemplePython]

As a hint for problem 3. Termination conditions are stated to be:
- - - -

(For avoidance of doubt, this refers to playing one 'full' game, which is complete upon termination, and termination occurs on the first occurrence of (a) result of coin toss equals $\text{Other}$ or (b) the player elects to stop.)

If you like, you may include an additional condition: (c) the carnival operator doesn't want you to play all day and so will stop you and force a "cash out" if you've hit a payoff of 1 million (or 1,000,001 or 1,000,002 -- in the case of overshoots).

- - - -

another hint: there are several ways to solve the problem. One technique that I particularly like would be familiar to Pascal, and, I think, Cauchy would approve.

 

[mfb]

If you like, you may include an additional condition: (c) the carnival operator doesn't want you to play all day and so will stop you and force a "cash out" if you've hit a payoff of 1 million (or 1,000,001 or 1,000,002 -- in the case of overshoots).

At least for me "find a solution that would profit from this idea" is much more difficult than the original problem. I know ways to solve the problem, but no way where considering a payoff of 1 million would be involved.

 

[lpetrich]

More on Problem 1

Spoiler

For a field F with N elements, the number of irreducible monic polynomials of degree n I call N(n), and I'd shown
$$ \sum_{\sum_k k m_k = n} \left( \prod_k P(N(k),m_k) \right) = N^n = \sum_{m|n} \frac{n}{m} N(n/m) $$
taking my final expression in my previous post and multiplying it by n.

This calls for a Möbius transform, where
$$ f(n) = \sum_{m|n} g(m) \longleftrightarrow g(n) = \sum_{m|n} \mu(m) f(n/m) $$
where $\mu(n)$ is the Möbius function of n.

Using it here gives
$$ N(n) = \frac{1}{n} \sum_{m|n} \mu(m) N^{n/m} $$
Since $\mu(n)$ can be negative as well as positive, proving that N(n) is always positive for N > 1 is a challenge.

 

[StoneTemplePython]

At least for me "find a solution that would profit from this idea" is much more difficult than the original problem. I know ways to solve the problem, but no way where considering a payoff of 1 million would be involved.

I could argue it either way as to which setup is more intuitive... which is why I put (c) as optional.

The original problem, literally interpreted, has a countable set of outcomes / state space. The use of (c) truncates that and makes the set have a finite number of outcomes-- which, I think, may be easier for some to work with.

 

[Zafa Pi]

Solution to #3
The average win for heads or tails is 2 with probability 4/5.
A risk neutral player will play as long as her expectation is positive. She will quit if her expectation is ≤ 0.
If she has accrued x, then her expectation for the next play 2⋅4/5 - x⋅1/5. That is positive for x < 8 and ≤ 0 for x for x ≥ 8.
Thus she will quit when x ≥ 8, assuming "other" has not occurred.

We must now determine the expected value of that strategy. Let p = 2/5.
If she gets to x = 7, then with prob 2p her expected win will be 9.
There are various ways to get to x= 7,
by 7 1's with prob p⁷, or
by 4 1's and a 3 with prob 5⋅p⁵, or
by 2 3's and a 1 with prob 3⋅p³.
Thus the expected win win via x = 7 is (p⁷ 2p + 5p⁵ 2p + 3p³2p)9.

She can also win by having x = 6 and getting a 3, and there are various ways to get x = 6,
by 6 1's with prob p⁶, or
by 3 1's and a 3 with prob 4p⁴, or
by 2 3's with prob p².
Each of these pay 9 with total prob = p⁷ + 4p⁵ + p³.

Finally, she can also win by having x = 5 and getting a 3. There are 2 ways of getting x = 5,
by 5 1's with prob p⁵, or
by 2 1's and a 3 with prob 3p³.
Each of these pay 8 with total prob = p⁶ + 3p⁴.

Adding the three cases we get the expected win to be 3.37 which is what a neutral player should pay.