How are finite fields constructed?
Here's another recent Math Stack Exchange answer I'm pleased with.
OP asked:
I know this question has been asked many times and there is good
information out there which has clarified a lot for me but I still
do not understand how the addition and multiplication tables for
!!GF(4)!! is constructed?
I've seen [links] but none explicity explain the construction and
I'm too new to be told "its an extension of !!GF(2)!!"
The only “reasonable” answer here is “get an undergraduate abstract
algebra text and read the chapter on finite fields”. Because come on,
you can't expect some random stranger to appear and write up a
detailed but short explanation at your exact level of knowledge.
But sometimes Internet Magic Lightning strikes and that's what you do
get! And OP set themselves up to be struck by magic lightning,
because you can't get a detailed but short explanation at your exact
level of knowledge if you don't provide a detailed but short
explanation of your exact level of knowledge — and this person did
just that. They understand finite fields of prime order, but not how
to construct the extension fields. No problem, I can explain that!
I had special fun writing
this answer because
I just love constructing extensions of finite
fields. (Previously: [1]
[2])
For any given !!n!!, there is at most one field with !!n!! elements: only one, if !!n!! is a power of a prime number (!!2, 3, 2^2, 5, 7, 2^3, 3^2, 11, 13, \ldots!!) and none otherwise (!!6, 10, 12, 14\ldots!!). This field with !!n!! elements is written as !!\Bbb F_n!! or as !!GF(n)!!.
Suppose we want to construct !!\Bbb F_n!! where !!n=p^k!!. When !!k=1!!, this is easypeasy: take the !!n!! elements to be the integers !!0, 1, 2\ldots p1!!, and the addition and multiplication are done modulo !!n!!.
When !!k>1!! it is more interesting. One possible construction goes like this:
The elements of !!\Bbb F_{p^k}!! are the polynomials $$a_{k1}x^{k1} + a_{k2}x^{k2} + \ldots + a_1x+a_0$$ where the coefficients !!a_i!! are elements of !!\Bbb F_p!!. That is, the coefficients are just integers in !!{0, 1, \ldots p1}!!, but with the understanding that the addition and multiplication will be done modulo !!p!!. Note that there are !!p^k!! of these polynomials in total.
Addition of polynomials is done exactly as usual: combine like terms, but remember that the the coefficients are added modulo !!p!! because they are elements of !!\Bbb F_p!!.
Multiplication is more interesting:
a. Pick an irreducible polynomial !!P!! of degree !!k!!. “Irreducible” means that it does not factor into a product of smaller polynomials. How to actually locate an irreducible polynomial is an interesting question; here we will mostly ignore it.
b. To multiply two elements, multiply them normally, remembering that the coefficients are in !!\Bbb F_p!!. Divide the product by !!P!! and keep the remainder. Since !!P!! has degree !!k!!, the remainder must have degree at most !!k1!!, and this is your answer.
Now we will see an example: we will construct !!\Bbb F_{2^2}!!. Here !!k=2!! and !!p=2!!. The elements will be polynomials of degree at most 1, with coefficients in !!\Bbb F_2!!. There are four elements: !!0x+0, 0x+1, 1x+0, !! and !!1x+1!!. As usual we will write these as !!0, 1, x, x+1!!. This will not be misleading.
Addition is straightforward: combine like terms, remembering that !!1+1=0!! because the coefficients are in !!\Bbb F_2!!:
$$\begin{array}{ccccc}
+ & 0 & 1 & x & x+1 \\ \hline
0 & 0 & 1 & x & x+1 \\
1 & 1 & 0 & x+1 & x \\
x & x & x+1 & 0 & 1 \\
x+1 & x+1 & x & 1 & 0
\end{array}
$$
The multiplication as always is more interesting. We need to find an irreducible polynomial !!P!!. It so happens that !!P=x^2+x+1!! is the only one that works. (If you didn't know this, you could find out easily: a reducible polynomial of degree 2 factors into two linear factors. So the reducible polynomials are !!x^2, x·(x+1) = x^2+x!!, and !!(x+1)^2 = x^2+2x+1 = x^2+1!!. That leaves only !!x^2+x+1!!.)
To multiply two polynomials, we multiply them normally, then divide by !!x^2+x+1!! and keep the remainder. For example, what is !!(x+1)(x+1)!!? It's !!x^2+2x+1 = x^2 + 1!!. There is a theorem from elementary algebra (the “division theorem”) that we can find a unique quotient !!Q!! and remainder !!R!!, with the degree of !!R!! less than 2, such that !!PQ+R = x^2+1!!. In this case, !!Q=1, R=x!! works. (You should check this.) Since !!R=x!! this is our answer: !!(x+1)(x+1) = x!!.
Let's try !!x·x = x^2!!. We want !!PQ+R = x^2!!, and it happens that !!Q=1, R=x+1!! works. So !!x·x = x+1!!.
I strongly recommend that you calculate the multiplication table yourself. But here it is if you want to check:
$$\begin{array}{ccccc}
· & 0 & 1 & x & x+1 \\ \hline
0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & x & x+1 \\
x & 0 & x & x+1 & 1 \\
x+1 & 0 & x+1 & 1 & x
\end{array}
$$
To calculate the unique field !!\Bbb F_{2^3}!! of order 8, you let the elements be the 8 seconddegree polynomials !!0, 1, x, \ldots, x^2+x, x^2+x+1!! and instead of reducing by !!x^2+x+1!!, you reduce by !!x^3+x+1!!. (Not by !!x^3+x^2+x+1!!, because that factors as !!(x^2+1)(x+1)!!.) To calculate the unique field !!\Bbb F_{3^2}!! of order 27, you start with the 27 thirddegree polynomials with coefficients in !!{0,1,2}!!, and you reduce by !!x^3+2x+1!! (I think).
The special notation !!\Bbb F_p[x]!! means the ring of all polynomials with coefficients from !!\Bbb F_p!!. !!\langle P \rangle!! means the ring of all multiples of polynomial !!P!!. (A ring is a set with an addition, subtraction, and multiplication defined.)
When we write !!\Bbb F_p[x] / \langle P\rangle!! we are constructing a thing called a “quotient” structure. This is a generalization of the process that turns the ordinary integers !!\Bbb Z!! into the modulararithmetic integers we have been calling !!\Bbb F_p!!. To construct !!\Bbb F_p!!, we start with !!\Bbb Z!! and then agree that two elements of !!\Bbb Z!! will be considered equivalent if they differ by a multiple of !!p!!.
To get !!\Bbb F_p[x] / \langle P \rangle!! we start with !!\Bbb F_p[x]!!, and then agree that elements of !!\Bbb F_p[x]!! will be considered equivalent if they differ by a multiple of !!P!!. The division theorem guarantees that of all the equivalent polynomials in a class, exactly one of them will have degree less than that of !!P!!, and that is the one we choose as a representative of its class and write into the multiplication table. This is what we are doing when we “divide by !!P!! and keep the remainder”.
A particularly important example of this construction is !!\Bbb R[x] / \langle x^2 + 1\rangle!!. That is, we take the set of polynomials with real coefficients, but we consider two polynomials equivalent if they differ by a multiple of !!x^2 + 1!!. By the division theorem, each polynomial is then equivalent to some firstdegree polynomial !!ax+b!!.
Let's multiply $$(ax+b)(cx+d).$$ As usual we obtain $$acx^2 + (ad+bc)x + bd.$$ From this we can subtract !!ac(x^2 + 1)!! to obtain the equivalent firstdegree polynomial $$(ad+bc) x + (bdac).$$
Now recall that in the complex numbers, !!(b+ai)(d + ci) = (bdac) + (ad+bc)i!!. We have just constructed the complex numbers,with the polynomial !!x!! playing the role of !!i!!.
[ Note to self: maybe write a separate article about what makes this a good answer, and how it is structured. ]
[Other articles in category /math/se]
permanent link
What does it mean to expand a function “in powers of x1”?
A recent Math Stack Excahnge post
was asked to expand the function !!e^{2x}!! in powers of !!(x1)!! and
was confused about what that meant, and what the point of it was.
I wrote an answer I liked,
which I am reproducing here.
You asked:
I don't understand what are we doing in this whole process
which is a fair question. I didn't understand this either when I first
learned it. But it's important for practical engineering reasons as
well as for theoretical mathematical ones.
Before we go on, let's see that your proposal is the wrong answer to
this question, because it is the correct answer, but to a different
question. You suggested:
$$e^{2x}\approx1+2\left(x1\right)+2\left(x1\right)^2+\frac{4}{3}\left(x1\right)^3$$
Taking !!x=1!! we get !!e^2 \approx 1!!, which is just wrong, since
actually !!e^2\approx 7.39!!. As a comment pointed out, the series you
have above is for !!e^{2(x1)}!!. But we wanted a series that adds up
to !!e^{2x}!!.
As you know, the Maclaurin series works here:
$$e^{2x} \approx 1+2x+2x^2+\frac{4}{3}x^3$$
so why don't we just use it? Let's try !!x=1!!. We get $$e^2\approx
1 + 2 + 2 + \frac43$$
This adds to !!6+\frac13!!, but the correct answer is actually around
!!7.39!! as we saw before. That is not a very accurate approximation.
Maybe we need more terms? Let's try ten:
$$e^{2x} \approx 1+2x+2x^2+\frac{4}{3}x^3 + \ldots +
\frac{8}{2835}x^9$$
If we do this we get !!7.3887!!, which isn't too far off. But it was a
lot of work! And we find that as !!x!! gets farther away from zero, the
series above gets less and less accurate. For example, take !!x=3.1!!,
the formula with four terms gives us !!66.14!!, which is dead wrong.
Even if we use ten terms, we get !!444.3!!, which is still way off. The
right answer is actually !!492.7!!.
What do we do about this? Just add more terms? That could be a lot of
work and it might not get us where we need to go. (Some Maclaurin
series just stop working at all too far from zero, and no amount of
terms will make them work.) Instead we use a different technique.
Expanding the Taylor series “around !!x=a!!” gets us a different series,
one that works best when !!x!! is close to !!a!! instead of when !!x!! is
close to zero. Your homework is to expand it around !!x=1!!, and I don't
want to give away the answer, so I'll do a different example. We'll
expand !!e^{2x}!! around !!x=3!!. The general formula is $$e^{2x} \approx
\sum \frac{f^{(i)}(3)}{i!} (x3)^i\tag{$\star$}\ \qquad \text{(when
$x$ is close to $3$)}$$
The !!f^{(i)}(x)!! is the !!i!!'th derivative of !! e^{2x}!! , which is
!!2^ie^{2x}!!, so the first few terms of the series above are:
$$\begin{eqnarray}
e^{2x} & \approx& e^6 + \frac{2e^6}1 (x3) + \frac{4e^6}{2}(x3)^2 +
\frac{8e^6}{6}(x3)^3\\
& = & e^6\left(1+ 2(x3) + 2(x3)^2 + \frac34(x3)^3\right)\\
& & \qquad \text{(when $x$ is close to $3$)}
\end{eqnarray}
$$
The first thing to notice here is that when !!x!! is exactly !!3!!,
this series is perfectly correct; we get !!e^6 = e^6!! exactly, even
when we add up only the first term, and ignore the rest. That's a
kind of useless answer because we already knew that !!e^6 = e^6!!.
But that's not what this series is for. The whole point of this
series is to tell us how different !!e^{2x}!! is from !!e^6!! when !!x!!
is close to, but not equal to !!3!!.
Let's see what it does at !!x=3.1!!. With only four terms we get
$$\begin{eqnarray}
e^{6.2} & \approx& e^6(1 + 2(0.1) + 2(0.1)^2 + \frac34(0.1)^3)\\
& = & e^6 \cdot 1.22075 \\
& \approx & 492.486
\end{eqnarray}$$
which is very close to the correct answer, which is !!492.7!!. And
that's with only four terms. Even if we didn't know an exact value
for !!e^6!!, we could find out that !!e^{6.2}!! is about !!22.075\%!!
larger, with hardly any calculation.
Why did this work so well? If you look at the expression !!(\star)!!
you can see: The terms of the series all have factors of the form
!!(x3)^i!!. When !!x=3.1!!, these are !!(0.1)^i!!, which becomes very
small very quickly as !!i!! increases. Because the later terms of the
series are very small, they don't affect the final sum, and if we
leave them out, we won't mess up the answer too much. So the
series works well, producing accurate results from only a few
terms, when !!x!! is close to !!3!!.
But in the Maclaurin series, which is around !!x=0!!, those
!!(x3)^i!! terms are !!x^i!! terms intead, and when !!x=3.1!!, they are
not small, they're very large! They get bigger as !!i!!
increases, and very quickly. (The !! i! !! in the denominator wins,
eventually, but that doesn't happen for many terms.) If we leave
out these many large terms, we get the wrong results.
The short answer to your question is:
Maclaurin series are only good for calculating functions when !!x!!
is close to !!0!!, and become inaccurate as !!x!! moves away from
zero. But a Taylor series around !!a!! has its “center” near !!a!!
and is most accurate when !!x!! is close to !!a!!.
[Other articles in category /math/se]
permanent link
Math.SE report 201508
I only posted three answers in August, but two of them were interesting.
In why this !!\sigma\pi\sigma^{1}!! keeps apearing in my group
theory book? (cycle
decomposition) the
querent asked about the “conjugation” operation that keeps cropping
up in group theory. Why is it important? I sympathize with this;
it wasn't adequately explained when I took group theory, and I had
to figure it out a long time later. Unfortunately I don't think I
picked the right example to explain it, so I am going to try again
now.
Consider the eight symmetries of the square. They are of five types:
 Rotation clockwise or counterclockwise by 90°.
 Rotation by 180°.
 Horizontal or vertical reflection
 Diagonal reflection
 The trivial (identity) symmetry
What is meant when I say that a horizontal and a vertical reflection
are of the same ‘type’? Informally, it is that the horizontal
reflection looks just like the vertical reflection, if you turn your
head ninety degrees. We can formalize this by observing that if we
rotate the square 90°, then give it a horizontal flip, then rotate it
back, the effect is exactly to give it a vertical flip. In notation,
we might represent the horizontal flip by !!H!!, the vertical flip by
!!V!!, the clockwise rotation by !!\rho!!, and the counterclockwise
rotation by !!\rho^{1}!!; then we have
$$ \rho H \rho^{1} = V$$
and similarly
$$ \rho V \rho^{1} = H.$$
Vertical flips do not look like diagonal flips—the diagonal flip leaves two of the corners in the same place, and the vertical flip does not—and indeed there is
no analogous formula with !!H!! replaced with one of the diagonal
flips. However, if !!D_1!! and !!D_2!! are the two diagonal flips,
then we do have
$$ \rho D_1 \rho^{1} = D_2.$$
In general, When !!a!! and !!b!! are
two symmetries, and there is some symmetry !!x!! for which
$$xax^{1} = b$$
we say that !!a!! is conjugate to !!b!!.
One can show that
conjugacy is an equivalence relation, which means that the symmetries
of any object can be divided into separate “conjugacy classes” such that two
symmetries are conjugate if and only if they are in the same class.
For the square, the conjugacy classes are the five I listed earlier.
This conjugacy thing is important for telling when two symmetries
are grouptheoretically “the same”, and have the same
grouptheoretic properties. For example, the fact that the
horizontal and vertical flips move all four vertices, while the
diagonal flips do not. Another example is that a horizontal flip is
selfinverse (if you do it again, it cancels itself out), but a 90°
rotation is not (you have to do it four times before it cancels
out.) But the horizontal flip shares all its properties with the
vertical flip, because it is the same if you just turn your head.
Identifying this sameness makes certain kinds of arguments much
simpler. For example, in counting
squares, I wanted to
count the number of ways of coloring the faces of a cube, and instead
of dealing with the 24 symmetries of the cube, I only needed to deal
with their 5 conjugacy classes.
The example I gave in my math.se answer was maybe less perspicuous. I
considered the symmetries of a sphere, and talked about how two
rotations of the sphere by 17° are conjugate, regardless of what axis
one rotates around. I thought of the square at the end, and threw it
in, but I wish I had started with it.
How to convert a decimal to a fraction
easily? was the
month's big winner. OP wanted to know how to take a decimal like
!!0.3760683761!! and discover that it can be written as
!!\frac{44}{117}!!. The right answer to this is of course to use
continued fraction theory, but I did not want to write a long
treatise on continued fractions, so I stripped down the theory to
obtain an algorithm that is slower, but much easier to understand.
The algorithm is just binary search, but with a twist. If you are looking for a
fraction for !!x!!, and you know !!\frac ab < x < \frac cd!!, then
you construct the mediant !!\frac{a+c}{b+d}!! and compare it with
!!x!!. This gives you a smaller interval in which to search for
!!x!!, and the reason you use the mediant instead of using
!!\frac12\left(\frac ab + \frac cd\right)!! as usual is that if you use the
mediant you are guaranteed to exactly nail all the best rational
approximations of !!x!!. This is the algorithm I
described a few years ago in your age as a fraction,
again; there the binary search proceeds
down the branches of the SternBrocot tree to find a fraction close
to !!0.368!!.
I did ask a question this month: I was looking for a simpler version
of the dogbone space
construction. The
dogbone space is a very peculiar counterexample of general topology,
originally constructed by R.H. Bing. I mentioned it here in
2007, and said, at the time:
[The paper] is on my desk, but I have not read this yet, and I may never.
I did try to read it, but I did not try very hard, and I did not
understand it. So my question this month was if there was a simpler
example of the same type. I did not receive an answer, just a
followup comment that no, there is no such example.
[Other articles in category /math/se]
permanent link
Math.SE report 201507
My overall SE posting volume was down this month, and not only did I
post relatively few interesting items, I've already written a whole
article about the most interesting
one. So this will be a short
report.
I already wrote up Building a box from smaller
boxes on the blog
here. But maybe I have a
couple of extra remarks. First, the other guy's proposed solution
is awful. It's long and complicated, which is forgivable if it had
answered the question, but it doesn't. And the key point is “blah
blah blah therefore code a solver which visits all configurations of
the search space”. Well heck, if this post had just been one
sentence that ended with “code a solver which visits all
configurations of the search space” I would not have any complaints
about that.
As an undergraduate I once gave a talk on this topic. One of my
examples was the problem of packing 31 dominoes into a chessboard
from which two squares have been deleted. There is a simple
combinatorial argument why this is impossible if the two deleted
squares are the same color, say if they are opposite corners: each
domino must cover one square of each color. But if you don't take
time to think about the combinatorial argument you could waste a lot
of time on computer search learning that there is no solution in
that case, and completely miss the deeper understanding that it
brings you. So this has been on my mind for a long time.
I wrote a few posts this month where I thought I gave good hints.
In How to scale an unit vector !!u!! in such way that !!a u\cdot
u=1!! where !!a!! is a
scalar I think I
did a good job identifying the original author's confusion; he was
conflating his original unit vector !!u!! and the scaled, leading
him to write !!au\cdot u=1!!. This is sure to lead to confusion. So
I led him to the point of writing !!a(bv)\cdot(bv)=1!! and let him
take it from there. The other proposed solution is much more rote
and mechanical. (“Divide this by that…”)
In Find numbers !!\overline{abcd}!! so that
!!\overline{abcd}+\overline{bcd}+\overline{cd}+d+1=\overline{dcba}!!
the OP got stuck partway through and I specifically addressed the
stuckness; other people solved the problem from the beginning. I
think that's the way to go, if the original proposal was never going
to work, especially if you stop and say why it was never going to
work, but this time OP's original suggestion was perfectly good and
she just didn't know how to get to the next step. By the way, the
notation !!\overline{abcd}!! here means the number
!!1000a+100b+10c+d!!.
In Help finding the limit of this series !!\frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \frac{1}{32} + \cdots!! it would
have been really easy to say “use the formula” or to analyze the
series de novo, but I think I almost hit the nail on the head
here: it's just like !!1+\frac12 + \frac{1}{4} + \frac{1}{8} +
\frac{1}{16} + \frac{1}{32} + \cdots!!, which I bet OP already
knows, except a little different. But I pointed out the wrong
difference: I observed that the first sequence is onefourth the
second one (which it is) but it would have been simpler to observe
that it's just the second one without the !!1+\frac12!!. I had to
review it just now to give the simpler explanation, but I sure wish
I'd thought of it at the time. Nobody else pointed it out either.
Best of all, would have been to mention both methods. If you can
notice both of them you can solve the problem without the advance
knowledge of the value of !!1+\frac12+\frac14+\ldots!!, because you
have !!4S = 1+\frac12 + S!! and then solve for !!S!!.
In Visualization of Rhombus made of Radii and
Chords it seemed
that OP just needed to see a diagram (“I really really don't see how
two circles can form a rhombus?”), so I drew one.
[Other articles in category /math/se]
permanent link
Math.SE report 201504
[ Notice: I originally published this report at the wrong URL. I
moved it so that I could publish the June 2015
report at that URL instead. If you're
seeing this for the second time, you might want to read the June
article instead. ]
A lot of the stuff I've written in the past couple of years has been
on Mathematics StackExchange. Some of it is pretty mundane, but some
is interesting. I thought I might have a little metadiscussion in
the blog and see how that goes. These are the noteworthy posts I made
in April 2015.
Languages and their relation :
help
is pretty mundane, but interesting for one reason: OP was confused
about a statement in a textbook, and provided a reference, which OPs
don't always do. The text used the symbol !!\subset_\ne!!. OP had
interpreted it as meaning !!\not\subseteq!!, but I think what was
meant was !!\subsetneq!!.
I dug up a copy of the text and groveled over it looking for the
explanation of !!\subset_\ne!!, which is not standard. There was
none that I could find. The book even had a section with a glossary
of notation, which didn't mention !!\subset_\ne!!. Math professors
can be assholes sometimes.
Is there an operation that takes !!a^b!! and !!a^c!!, and returns
!!a^{bc}!!
is more interesting. First off, why is this even a reasonable
question? Why should there be such an operation? But note that
there is an operation that takes !!a^b!! and !!a^c!! and returns
!!a^{b+c}!!, namely, multiplication, so it's plausible that the
operation that OP wants might also exist.
But it's easy to see that there is no operation that takes !!a^b!!
and !!a^c!! and returns !!a^{bc}!!: just observe that although
!!4^2=2^4!!, the putative operation (call it !!f!!) should take
!!f(2^4, 2^4)!! and yield !!2^{4\cdot4} = 2^{16} = 65536!!, but it
should also take !!f(4^2, 4^2)!! and yield !!4^{2\cdot2} = 2^4 =
256!!. So the operation is not welldefined. And you can take this
even further: !!2^4!! can be written as !!e^{4\log 2}!!, so !!f!!
should also take !!f(e^{2\log 4}, e^{2\log 4})!! and yield
!!e^{4(\log 4)^2} \approx 2180.37!!.
They key point is that the representation of a number, or even an
integer, in the form !!a^b!! is not unique. (Jargon:
"exponentiation is not injective".) You can raise !!a^b!!, but
having done so you cannot look at the result and know what !!a!!
and !!b!! were, which is what !!f!! needs to do.
But if !!f!! can't do it, how can multiplication do it when it
multiplies !!a^b!! and !!a^c!! and gets !!a^{b+c}!!? Does it
somehow know what !!a!! is? No, it turns out that it doesn't need
!!a!! in this case. There is something magical going on there,
ultimately related to the fact that if some quantity is increasing
by a factor of !!x!! every !!t!! units of time, then there is some
!!t_2!! for which it is exactly doubling every !!t_2!! units of
time. Because of this there is a marvelous group homomophism $$\log
: \langle \Bbb R^+, \times\rangle \to \langle \Bbb R ,+\rangle$$ which
can change multiplication into addition without knowing what the
base numbers are.
In that thread I had a brief argument with someone who thinks that
operators apply to expressions rather than to numbers. Well, you
can say this, but it makes the question trivial: you can certainly
have an "operator" that takes expressions !!a^b!! and !!a^c!! and
yields the expression !!a^{bc}!!. You just can't expect to apply
it to numbers, such as !!16!! and !!16!!, because those numbers are
not expressions in the form !!a^b!!. I remembered the argument
going on longer than it did; I originally ended this paragraph with
a lament that I wasted more than two comments on this guy, but
looking at the record, it seems that I didn't. Good work,
Mr. Dominus.
how 1/0.5 is equal to
2?
wants a simple explanation. Very likely OP is a primary school
student. The question reminds me of a similar question, asking why
the long division algorithm is the way it
is. Each
of these is a failure of education to explain what division is
actually doing. The long division answer is that long division is
an optimization for repeated subtraction; to divide !!450\div 3!!
you want to know how many shares of three cookies each you can get
from !!450!! cookies. Long division is simply a notation for
keeping track of removing !!100!! shares, leaving !!150!! cookies,
then !!5\cdot 10!! further shares, leaving none.
In this question there was a similar answer. !!1/0.5!! is !!2!!
because if you have one cookie, and want to give each kid a share
of !!0.5!! cookies, you can get out two shares. Simple enough.
I like division examples that involve giving cookies to kids,
because cookies are easy to focus on, and because the motivation for
equal shares is intuitively understood by everyone who has kids, or
who has been one.
There is a general pedagogical principle that an ounce of examples
are worth a pound of theory. My answer here is a good example of
that. When you explain the theory, you're telling the student how
to understand it. When you give an example, though, if it's the
right example, the student can't help but understand it, and when
they do they'll understand it in their own way, which is better than
if you told them how.
How to read a cycle
graph?
is interesting because hapless OP is asking for an explanation of a
particularly strange diagram from Wikipedia. I'm familiar with the
eccentric Wikipedian who drew this, and I was glad that I was around
to say "The other stuff in this diagram is nonstandard stuff that
the somewhat eccentric author made up. Don't worry if it's not
clear; this author is notorious for that."
In Expected number of die tosses to get something less than
5,
OP calculated as follows: The first die roll is a winner !!\frac23!!
of the time. The second roll is the first winner
!!\frac13\cdot\frac23!! of the time. The third roll is the first
winner !!\frac13\cdot\frac13\cdot\frac23!! of the time. Summing the series
!!\sum_n \frac23\left(\frac13\right)^nn!! we eventually obtain the
answer, !!\frac32!!. The accepted answer does it this way also.
But there's a much easier way to solve this problem. What we really
want to know is: how many rolls before we expect to have seen one
good one? And the answer is: the expected number of winners per die
roll is !!\frac23!!, expectations are additive, so the expected
number of winners per !!n!! die rolls is !!\frac23n!!, and so we
need !!n=\frac32!! rolls to expect one winner. Problem solved!
I first discovered this when I was around fifteen, and wrote about
it here a few years ago.
As I've mentioned
before, this is
one of the best things about mathematics: not that it works, but
that you can do it by whatever method that occurs to you and you get
the same answer. This is where mathematics pedagogy goes wrong most
often: it proscribes that you must get the answer by method X,
rather than that you must get the answer by hook or by crook. If
the student uses method Y, and it works (and if it is correct) that
should be worth full credit.
Bad instructors always say "Well, we need to test to see if the
student knows method X." No, we should be testing to see if the
student can solve problem P. If we are testing for method X, that
is a failure of the test or of the curriculum. Because if method X
is useful, it is useful because for some problems, it is the only
method that works. It is the instructor's job to find one of these
problems and put it on the test. If there is no such problem, then
X is useless and it is the instructor's job to omit it from the
curriculum. If Y always works, but X is faster, it is the
instructor's job to explain this, and then to assign a problem for
the test where Y would take more time than is available.
I see now I wrote the same thing in
2006. It bears repeating.
I also said it again a couple of years ago on math.se
itself
in reply to a similar comment by Brian Scott:
If the goal is to teach students how to write proofs by induction,
the instructor should damned well come up with problems for which
induction is the best approach. And if even then a student comes
up with a different approach, the instructor should be
pleased. ... The directions should not begin [with "prove by
induction"]. I consider it a failure on the part of the instructor
if he or she has to specify a technique in order to give students
practice in applying it.
[Other articles in category /math/se]
permanent link
Math.SE report 201505
A lot of the stuff I've written in the past couple of years has been
on math.StackExchange. Some of it is pretty mundane, but some is
interesting. My summary of April's interesting posts was
wellreceived, so here are the noteworthy posts I made in May 2015.
What matrix transforms !!(1,0)!! into !!(2,6)!! and tranforms
!!(0,1)!! into
!!(4,8)!!? was a
little funny because the answer is $$\begin{pmatrix}2 & 4 \\ 6 & 8
\end{pmatrix}$$ and yeah, it works exactly like it appears to,
there's no trick. But if I just told the guy that, he might feel
unnecessarily foolish. I gave him a method for solving the problem
and figured that when he saw what answer he came up with, he might
learn the thing that the exercise was designed to teach him.
Is a “network topology'” a topological
space?
is interesting because several people showed up right away to say
no, it is an abuse of terminology, and that network topology really
has nothing to do with mathematical topology. Most of those comments
have since been deleted. My answer was essentially: it is
topological, because just as in mathematical topology you care about
which computers are connected to which, and not about where any of
the computers actually are.
Nobody constructing a token ring network thinks that it has to be a
geometrically circular ring. No, it only has to be a topologically
circular ring. A square is fine; so is a triangle; topologically
they are equivalent, both in networking and in mathematics. The
wires can cross, as long as they don't connect at the crossings.
But if you use something that isn't topologically a ring, like say
a line or a star or a tree, the network doesn't work.
The term “topological” is a little funny. “Topos” means “place”
(like in “topography” or “toponym”) but in topology you don't care
about places.
Is there a standard term for this generalization of the Euler
totient function?
was asked by me. I don't include all my answers in these posts, but
I think maybe I should have a policy of including all my questions.
This one concerned a simple concept from number theory which I was
surprised had no name: I wanted !!\phi_k(n)!! to be the number of
integers !!m!! that are no larger than !!n!! for which !!\gcd(m,n) =
k!!. For !!k=1!! this is the famous Euler totient function, written
!!\varphi(n)!!.
But then I realized that the reason it has no name is that it's
simply !!\phi_k(n) = \varphi\left(\frac n k\right)!! so there's no need
for a name or a special notation.
As often happens, I found the answer myself shortly after I asked
the question. I wonder if the reason for this is that my time to
come up with the answer is Poissondistributed. Then if I set a time
threshold for how long I'll work on the problem before asking about
it, I am likely to find the answer to almost any question that
exceeds the threshold shortly after I exceed the threshold. But if
I set the threshold higher, this would still be true, so there is
no way to win this particular game. Good feature of this theory: I
am off the hook for asking questions I could have answered myself.
Bad feature: no real empirical support.
how many ways can you divide 24 people into groups of
two? displays a
few oddities, and I think I didn't understand what was going on at
that time. OP has calculated the first few special cases:
1:1 2:1 3:3 4:3 5:12 6:15
which I think means that there is one way to divide 2 people into
groups of 2, 3 ways to divide 4 people, and 15 ways to divide 6
people. This is all correct! But what could the 1:1, 3:3, 5:12
terms mean? You simply can't divide 5 people into groups of 2.
Well, maybe OP was counting the extra odd person left over as a sort
of group on their own? Then odd values would be correct; I didn't
appreciate this at the time.
But having calculated 6 special cases correctly, why can't OP
calculate the seventh? Perhaps they were using brute force: the
next value is 48, hard to bruteforce correctly if you don't have a
enough experience with combinatorics.
I tried to suggest a general strategy: look at special cases, and
not by brute force, but try to analyze them so that you can come
up with a method for solving them. The method is unnecessary for
the small cases, where brute force enumeration suffices, but you can
use the brute force enumeration to check that the method is
working. And then for the larger cases, where brute force is
impractical, you use your method.
It seems that OP couldn't understand my method, and when they tried
to apply it, got wrong answers. Oh well, you can lead a horse to
water, etc.
The other pathology here is:
I think I did what you said and I got 1.585times 10 to the 21
for the !!n=24!! case. The correct answer is
$$23\cdot21\cdot19\cdot17\cdot15\cdot13\cdot11\cdot9\cdot7\cdot5\cdot3\cdot1
= 316234143225 \approx 3.16\cdot 10^{11}.$$ OP didn't explain how
they got !!1.585\cdot10^{21}!! so there's not much hope of
correcting their weird error.
This is someone who probably could have been helped in person, but
on the Internet it's hopeless. Their problems are Internet
communication problems.
Lambda calculus
typing isn't
especially noteworthy, but I wrote a fairly detailed explanation of
the algorithm that Haskell or SML uses to find the type of an
expression, and that might be interesting to someone.
I think Special representation of a
number is the
standout post of the month. OP speculates that, among numbers of
the form !!pq+rs!! (where !!p,q,r,s!! are prime), the choice of
!!p,q,r,s!! is unique. That is, the mapping !!\langle
p,q,r,s\rangle \to pq+rs!! is reversible.
I was able to guess that this was not the case within a couple of
minutes, replied pretty much immediately:
I would bet money against this representation being unique.
I was sure that a simple computer search would find
counterexamples. In fact, the smallest is !!11\cdot13 + 19\cdot 29
= 11\cdot 43 + 13\cdot 17 = 694!! which is small enough that you
could find it without the computer if you are patient.
The obvious lesson to learn from this is that many elementary
conjectures of this type can be easily disproved by a trivial
computer search, and I frequently wonder why more amateur
mathematicians don't learn enough computer programming to
investigate this sort of thing. (I wrote recently on the topic of
An ounce of theory is worth a pound of search
, and this is an interesting
counterpoint to that.)
But the most interesting thing here is how I was able to instantly
guess the answer. I explained in some detail in the post. But the
basic line of reasoning goes like this.
Additive properties of the primes are always distributed more or
less at random unless there is some obvious reason why they can't
be. For example, let !!p!! be prime and consider !!2p+1!!. This
must have exactly one of the three forms !!3n1, 3n,!! or !!3n+1!!
for some integer !!n!!. It obviously has the form !!3n+1!! almost
never (the only exception is !!p=3!!). But of the other two forms
there is no obvious reason to prefer one over the other, and indeed
of the primes up to 10,000, 611 are of the type !!3n!! and and 616
are of the type !!3n1!!.
So we should expect the value !!pq+rs!! to be distributed more or
less randomly over the set of outputs, because there's no obvious
reason why it couldn't be, except for simple stuff, like that it's
obviously almost always even.
So we are throwing a bunch of balls at random into bins, and the
claim is that no bin should contain more than one ball. For that to
happen, there must be vastly more bins than balls. But the bins are
numbers, and primes are not at all uncommon among numbers, so the
number of bins isn't vastly larger, and there ought to be at least
some collisions.
In fact, a more careful analysis, which I wrote up on the site,
shows that the number of balls is vastly larger—to have them be
roughly the same, you would need primes to be roughly as common as
perfect squares, but they are far more abundant than that—so as you
take larger and larger primes, the number of collisions increases
enormously and it's easy to find twenty or more quadruples of primes
that all map to the same result. But I was able to predict this
after a couple of minutes of thought, from completely elementary
considerations, so I think it's a good example of Lower Mathematics
at work.
This is an example of a fairly common pathology of math.se
questions: OP makes a conjecture that !!X!! never occurs or that
there are no examples with property !!X!!, when actually !!X!!
almost always occurs or every example has property !!X!!.
I don't know what causes this. Rik Signes speculates that it's just
wishful thinking: OP is doing some project where it would be useful
to have !!pq+rs!! be unique, so posts in hope that someone will tell
them that it is. But there was nothing more to it than baseless
hope. Rik might be right.
[ Addendum 20150619: A previous version of this article included the delightful typo “mathemativicians”. ]
[Other articles in category /math/se]
permanent link
Math.SE report 201506
[ This page originally held the report for April
2015, which has moved. It now contains
the report for June 2015. ]
Is “smarter than” a transitive
relationship?
concerns a hypothetical "is smarter than" relation with the
following paradoxicalseeming property:
most X's are smarter than most Y's, but most Y's are such that it
is not the case that most X's are smarter than it.
That is, if !!\mathsf Mx.\Phi(x)!! means that most !!x!! have property
!!\Phi!!, then we want both $$\mathsf Mx.\mathsf My.S(x, y)$$ and
also $$\mathsf My.\mathsf Mx.\lnot S(x, y).$$
“Most” is a little funny here: what does it mean? But we can pin it
down by supposing that there are an infinite number of !!x!!es and
!!y!!s, and agreeing that most !!x!! have property !!P!! if there
are only a finite number of exceptions. For example, everyone
should agree that most positive integers are larger than 7 and that
most prime numbers are odd. The jargon word here is that we are
saying that a subset contains “most of” the elements of a larger set
if it is cofinite.
There is a model of this property, and OP reports that they asked
the prof if this was because the "smarter than" relation !!S(x,y)!!
could be antitransitive, so that one might have !!S(x,y), S(y,z)!!
but also !!S(z,x)!!. The prof said no, it's not because of that,
but the OP want so argue that it's that anyway. But no, it's not
because of that; there is a model that uses a perfectly simple
transitive relation, and the nontransitive thing nothing but a
distraction. (The model maps the !!x!!es and !!y!!s onto numbers,
and says !!x!! is smarter than !!y!! if its number is bigger.)
Despite this OP couldn't give up the idea that the model exists
because of intransitive relations. It's funny how sometimes people
get stuck on one idea and can't let go of it.
How to generate a random number between 1 and 10 with a sixsided
die? was a lot of
fun and attracted several very good answers. Topscoring is Jack
D'Aurizio's, which proposes a completely straightforward method:
roll once to generate a bit that selects !!N=0!! or !!N=5!!, and
then roll again until you get !!M\ne 6!!, and the result is !!N+M!!.
But several other answers were suggested, including two by me, one
explaining the general technique of arithmetic
coding, which I'll
probably refer back to in the future when people ask similar
questions. Don't miss NovaDenizen's clever simplification of
arithmetic coding,
which I want to think about more, or D'Aurizio's suggestion that if
you threw the die into a Vshaped trough, it would land with one
edge pointing up and thus select a random number from 1 to 12 in a
single throw.
Interesting question: Is there an easytoremember mapping from
edges to numbers from 1–12? Each edge is naturally identified by a
pair of distinct integers from 1–6 that do not add to 7.
The oddlyphrased Category theory with objects as logical
expressions over !!{\vee,\wedge,\neg}!! and morphisms
as? asks if there is
a standard way to turn logical expressions into a category, which
there is: you put an arrow from !!A\to B!! for each proof that !!A!!
implies !!B!!; composition of arrows is concatenation of proofs, and
identity arrows are empty proofs. The categorial product,
coproduct, and exponential then correspond to !!\land, \lor, !! and
!!\to!!.
This got me thinking though. Proofs are properly not lists, they are
trees, so it's not entirely clear what the concatenation operation
is. For example, suppose proof !!X!! concludes !!A!! at its root
and proof !!Y!! assumes !!A!! in more than one leaf. When you
concatenate !!X!! and !!Y!! do you join all the !!A!!'s, or what? I
really need to study this more. Maybe the Lambek and Scott book
talks about it, or maybe the Goldblatt Topoi book, which I actually
own. I somehow skipped most of the Cartesian closed category stuff,
which is an oversight I ought to correct.
In Why is the Ramsey`s theorem a generalization of the Pigeonhole
principle I gave
what I thought was a terrific answer, showing how Ramsey's graph
theorem and the pigeonhole principle are both special cases of
Ramsey's hypergraph theorem. This might be my favorite answer of
the month. It got several upvotes, but OP preferred a different
answer, with fewer details.
There was a thread a while
back about theorems
which are generalizations of other theorems in nonobvious ways. I
pointed out the Yoneda lemma was a generalization of Cayley's
theorem from group theory. I see that nobody mentioned the Ramsey
hypergraph theorem being a generalization of the pigeonhole
principle, but it's closed now, so it's too late to add it.
In Why does the Deduction Theorem use
Union? I explained
that the English word and actually has multiple meanings. I know I've
seen this discussed in elementary logic texts but I don't remember
where.
Finally, Which is the largest power of natural number that can be
evaluated by
computers? asks if
it's possible for a computer to calculate !!7^{120000000000}!!. The
answer is yes, but it's nontrivial and you need to use some tricks.
You have to use the multiplyingbysquaring trick, and for the
squarings you probably want to do the multiplication with DFT. OP
was dissatistifed with the answer, and seemed to have some axe to
grind, but I couldn't figure out what it was.
[Other articles in category /math/se]
permanent link
