Wikipedia:Reference desk/Archives/Mathematics/2008 May 13

Mathematics desk
< May 12	<< Apr | May | Jun >>	May 14 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 13

Unique Factorization Domains

Suppose I have a ring extension of Z, say Z[w].

• How can I tell whether or not Z[w] is a unique factorization domain?
• What if w happens to be a root of 1? Are there tables that tell me the answer?

mike40033 (talk) 01:05, 13 May 2008 (UTC)

I'm learning about this too at the moment, you might be interested in the articles about the Stark-Heegner theorem and the Cyclotomic fields. -- Xedi (talk) 01:21, 13 May 2008 (UTC)

For your last question, Z[w] is a UFD iff it has class number 1, so the table you want is A061653 at the OEIS. According to that, there's a more extensive table in ' L. C. Washington, Introduction to Cyclotomic Fields'. Algebraist 13:48, 14 May 2008 (UTC)

Having checked that book myself, I now have the complete answer to your second question: adjoining a primitive nth root of unity to the integers gives a unique factorization domain iff n is one of 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 40, 42, 44, 45, 48, 50, 54, 60, 66, 70, 84, 90. Algebraist 14:08, 14 May 2008 (UTC)

So $\mathbb {Z} [\zeta _{23}]$ is the smallest of these which is not a UFD. How do we find an element with two distinct factorizations? kfgauss (talk) 19:57, 14 May 2008 (UTC)

I think number theory books are likely to have pretty examples, but if you just want any old example: Factor the ideal (2) into prime ideals (2,x) and (2,y). Then x*y is in (2), so x*y = 2*z with z in the ring. 2 is irreducible, but neither x nor y is a multiple of 2, since (2,x) is not (2). By computer x, y, and z can be chosen irreducible (x=1+w^2+w^4+w^5+w^6+w^10+w^11, y=1+w+w^5+w^6+w^7+w^9+w^11, z=w^5+w^6+w^7+w^9+w^10+3*w^11+w^12+w^13+w^15+w^16+w^17), but it's been too long for me to remember if it can always be chosen that way (for arbitrary prime ideals in number rings). According to the computer, {1,2,x,y,z,x*y} are the only divisors up to units of x*y. JackSchmidt (talk) 23:09, 14 May 2008 (UTC)

I don't understand... are you taking w as a primitive 23rd root of unity? Just looking at them, it doesn't seem that x*y=2z... shouldn't x*y start with a 1, for a start? --Tango (talk) 23:29, 14 May 2008 (UTC)

I haven't done the complete calculation (that's what JackSchmidt's computer is for), for the initial 1 cancels with a $\sum _{i=1}^{22}w^{i}$. There's a lot of cancellation going on. Algebraist 00:41, 15 May 2008 (UTC)

Yes, w is a primitive 23rd root of unity. I think number theory texts will have much prettier examples. In principal, no calculations are needed to understand my example (you don't need to know the values of x,y,z), as long as you believe 2 is irreducible in Z[w]. If this argument is not familiar, then reduced cases are probably easier: Factor (2) in Z[sqrt(-5)] as (2,x)*(2,y), then x*y=2*z, 2 is irreducible, and 2 cannot divide x or y. In fact, in this case you can take x=y=1+sqrt(-5), and z=-2+sqrt(-5). JackSchmidt (talk) 03:22, 15 May 2008 (UTC)

Ok, I felt bad and dusted off a number theory book myself. Edwards's "genetic" (historical) introduction to algebraic number theory, "Fermat's Last Theorem" is quite good, and has detailed information on Q[w], both historical and computational. At any rate, it works an example similar to mine, but also notes they worked much too hard, since 47*139 is divisible by 1-z+z^21, but N(47)=47^22, N(139)=139^22, and N(1-z+z^21)=47*139 divides neither. He has already shown that no element of Z[w] has norm 47, so 1-z+z^21 is irreducible, and yet divides neither 47 nor 139, so unique factorization fails. In this example though, 47 is not irreducible. This is page 105, section 4.4, the work of Kummer. JackSchmidt (talk) 03:51, 15 May 2008 (UTC)

Thanks for the great examples! Did you somehow know (2) would fail to be prime, or is it simply a likely guess (which you then confirm with your computer algebra program)? kfgauss (talk) 16:47, 15 May 2008 (UTC)

If you asking "how did Jack think about it?", then yes: (2) almost always factors, and I just asked the computer if this was some bizarre exception. Had it not factored (if someone had perversely asked for 29'th roots of unity instead), then I would have just tried (3), and then when that didn't work, (5). If you are asking, "how should an intelligent person think about this?", then consider a maximal ideal M containing 2R in your ring R=Z[w]. Then R/M is a field in which 1+1=0, since 1+1=2 is in M. Now R is generated by 1 and w, and w is a root of (x^23-1)/(x-1), so R/M is a field of characteristic 2 generated by an element that is a root of x^23-1. Now the field F of 2^11 elements is such a field since 23 divides 2^11-1, and the nonzero elements of F are a cyclic group of order 2^11-1. Since F is a Galois extension of Z/2Z, it is the splitting field of x^23-1 over Z/2Z, and so R/M is contained as a subfield of F (indeed F=R/M). In particular, R/M has at most 2^11 elements, but R/2R has 2^22 elements, so M properly contains 2R. Since R is a Dedekind domain, M divides 2R, and 2R factors. JackSchmidt (talk) 20:26, 15 May 2008 (UTC)

Neat. I notice 29 divides 5^14-1. Thanks for all the details. kfgauss (talk) 07:21, 16 May 2008 (UTC)

Gerschgorin Theorem and Taussky's Result

Okay, so in my numerical analysis class, studying for the finals, I came across the Gerschgorin criterion. One of the exercises is the proof of the criterion which is split up into three parts. I have proved the first two parts but the third one (which I learned later is called the Taussky's theorem), I can't get. Here is everything I have done:

Let $C=(c_{i,j})$ be an arbitrary $d\times d$ singular complex matrix.
Then there exists a nonzero $x$ such that $Cx=0$.
Choose $l\in \{1,2,...,d\}$ such that $|x_{l}|=\max |x_{j}|$.
This maximal element is of course, nonzero.
By considering the $l$th row of $Cx$, I have already proven that
$|c_{l,l}|\leq \sum _{j=1,j\neq l}^{d}|c_{l,j}|$.

Next, taking a dxd matrix B and letting $\lambda$ be an arbitrary eigenvalue of B.
Substituting, $C=B-\lambda I$, I have also shown that $\lambda$ is in a Gerschgorin disc $S_{l}$ where
$S_{l}=\{z\in \mathbb {C} :|z-b_{i,i}|\leq \sum _{j=1,j\neq i}^{d}|b_{i,j}|\}$
And since, $\lambda$ was an arbitrary eigenvalue of B, the entire spectrum of B is contained the union of all the Gerschgorin discs.

Now here is the problem which I can't get. Let us suppose that the matrix B is irreducible and the previous inequality holds as an equality, i.e.
$|c_{l,l}|=\sum _{j=1,j\neq l}^{d}|c_{l,j}|$
for some $l$ between 1 and d. I need to show that this equality implies that
$|c_{k,k}|=\sum _{j=1,j\neq l}^{d}|c_{k,j}|$ for all k between 1 and d.
This would imply that if an eigenvalue is on the boundary of one Gerschgorin disc, then that eigenvalue will be on the boundary of all Gerschgorin discs. Any ideas on how to prove it? I have looked in several books but everyone just states it and calls it a famous result but no one proves it.A Real Kaiser (talk) 05:51, 13 May 2008 (UTC)

Proceed as in your proof of the first step and get to the point $|c_{l,l}||x_{l}|\leq \sum _{j=1,j\neq l}^{d}|c_{l,j}||x_{j}|$. Now if we have the equality you mention, what does that mean about those $x_{j}$'s for which $c_{l,j}\neq 0$? Now use that irreducibility is equivalent to strong connectivity of the directed graph with d vertices with an edge from vertex i to vertex j if and only if $c_{i,j}\neq 0$. kfgauss (talk) 07:16, 13 May 2008 (UTC)

Proving Integrability

On a completely different note, I am trying to prove some properties for this function.
Let $f:[0,1]\rightarrow [0,1]$ be defined as $f(x)={\begin{cases}[1/x]^{-1},&{\mbox{if }}x\in (0,1]\\0,&{\mbox{if }}x=0\end{cases}}$
where [x] is the truncation function (i.e. [x]=the integer part of x). Notice that at each unit fraction, the function has a jump discontinuity and in between, the function is a constant. We have already had some discussion about this function but now I am trying to prove that this function is Riemann integrable. Here are some facts that I proved:

Fact I

$f(x)$ is a non-decreasing function
Proof:
Let $x>y$

$\Rightarrow 1/x<1/y$

$\Rightarrow [1/x]\leq [1/y]$

$\Rightarrow [1/x]^{-1}\geq [1/y]^{-1}$

$\Rightarrow f(x)\geq f(y)$.

Fact II

$f(x)$ is continuous at $x=0$ from the right.

Proof:Let $\epsilon >0$ be given and then let $\delta =\epsilon /2$.

$x-0<\delta$

$\Rightarrow x<\delta$

$\Rightarrow x<\epsilon /2$

$\Rightarrow 1/x>2/\epsilon$

$\Rightarrow [1/x]\geq 2/\epsilon$ (for $\epsilon$ sufficiently small)

$\Rightarrow [1/x]^{-1}\leq \epsilon /2<\epsilon$

$\Rightarrow f(x)<\epsilon$

$\Rightarrow f(x)-0<\epsilon$

$\therefore \lim _{x\rightarrow 0^{+}}f(x)=f(0^{+})=f(0)=0$

Fact III

$f(x)$ is Riemann integrable. This will be shown by proving that for every $\epsilon >0$, we can find a partition p of [0,1] such that the upper sum U(f,p) minus the lower sum L(f,p) using p, is smaller than $\epsilon$.

Proof: For a given $\epsilon >0$, let $\epsilon _{1}=\epsilon /4$, and let N=the largest integer less than or equal to 1/$\epsilon _{1}$. This gives us that 1/N will be the next unit fraction. Hence x=1/N will be the next point (on the right) after $x=\epsilon _{1}$ where $f(x)$ will have a jump discontinuity. Let $\epsilon _{2}=\epsilon _{1}/2N$ and let the partition be

$P=\{0,\epsilon _{1},{\frac {1}{N}}-\epsilon _{2},{\frac {1}{N}}+\epsilon _{2},{\frac {1}{N-1}}-\epsilon _{2},{\frac {1}{N-1}}+\epsilon _{2},...,{\frac {1}{3}}-\epsilon _{2},{\frac {1}{3}}+\epsilon _{2},{\frac {1}{2}}-\epsilon _{2},{\frac {1}{2}}+\epsilon _{2},1\}$

This is a perfectly valid partition, because the division by 2N ensures that none of the points go out of order. The intervals will not overlap. The point of the first fact was to make the Riemann evaluation easier. Since the function is nondecreasing, in order evaluate the area of a Riemann rectangle, for the upper sum, we simply take the value of the function on the right endpoint, and for the lower sum, we simply take the value of the function at the left endpoint. Both facts also show (for my teacher) that the function does NOT become unbounded as x goes to zero. In fact, if we extend the function to the interval [-1,1], the limit from the left as x goes to zero also exists so I can show that the function is actually continuous at x=0. But, that is just something extra.

Now when the difference between the upper sum and the lower sum is taken, the rectangles which fall on the flat region, with the base being of the form $x={\frac {1}{n}}+\epsilon _{2}$ to $x={\frac {1}{n-1}}-\epsilon _{2}$ cancel out because the upper sum is the same as the lower sum. The same thing happens with the last rectangle. The only rectangles that remain are the columns of width $2\epsilon _{2}$ which have the jump discontinuity in the middle.

So,
$U(f,p)-L(f,p)={\frac {1}{N}}\epsilon _{1}+\left({\frac {1}{N-1}}-{\frac {1}{N}}\right)2\epsilon _{2}+\left({\frac {1}{N-2}}-{\frac {1}{N-1}}\right)2\epsilon _{2}+\cdots +\left({\frac {1}{3}}-{\frac {1}{4}}\right)2\epsilon _{2}+\left({\frac {1}{2}}-{\frac {1}{3}}\right)2\epsilon _{2}+\left(1-{\frac {1}{2}}\right)2\epsilon _{2}$

$U(f,p)-L(f,p)={\frac {1}{N}}\epsilon _{1}+\left({\frac {1}{(N-1)(N)}}\right)2\epsilon _{2}+\left({\frac {1}{(N-2)(N-1)}}\right)2\epsilon _{2}+\cdots +\left({\frac {1}{12}}\right)2\epsilon _{2}+\left({\frac {1}{6}}\right)2\epsilon _{2}+\left({\frac {1}{2}}\right)2\epsilon _{2}$

Since height of each rectangle is less than or equal to one, and the number of terms with $2\epsilon _{2}$ is precisely N-1, we have that

$U(f,p)-L(f,p)\leq \epsilon _{1}+\underbrace {2\epsilon _{2}+2\epsilon _{2}+\cdots +2\epsilon _{2}+2\epsilon _{2}+2\epsilon _{2}} _{N-1}$

$U(f,p)-L(f,p)\leq \epsilon _{1}+(N-1)(2\epsilon _{2})\leq \epsilon _{1}+N(2\epsilon _{2})=\epsilon _{1}+N\left({\frac {2\epsilon _{1}}{2N}}\right)=\epsilon _{1}+\epsilon _{1}=\epsilon /2<\epsilon$.

Therefore, the function $f(x)$ is Riemann integrable on the interval [0,1]. The reason, I put all of this up is that I just want to run it by a couple of people here to make sure that I have not made a stupid mistake and to see if this is "rigorous" enough. I will be presenting this to him (and maybe we can finally settle this argument once and for all about this function being Riemann integrable) and he is very particular about rigor. So, do you guys think that am I missing out some particular detail which I should include or is this good enough for a rigorous Mathematical argument? Any comments and suggestion will be welcome about the proof of all three facts. The third one is the most important one, of course. In addition, in the proof of the second fact, in line three, it is obvious that the line is true for a sufficiently small epsilon but how can I write that better? I don't really like it the way I have it but I need it there. Thanks everyone!A Real Kaiser (talk) 09:33, 13 May 2008 (UTC)

In case you don't know, any monotone bounded function on a bounded real interval is Riemann integrable. This is easy to prove (at least assuming Riemann's integrability criterion, which you seem to be doing): pick an equal width partition of mesh $\delta$, and the difference between the upper and lower Darboux sums is $(f(b)-f(a))\delta$. Your proof of III may be a special case of this argument; I don't know, as I haven't read it. Algebraist 10:59, 13 May 2008 (UTC)

Your proof of II is flawed: it is not the case that x < epsilon/2 implies floor(1/x) is at least 2/epsilon for sufficiently small epsilon. You can conclude, however, that floor(1/x) is at least 2/epsilon - 1, which is at least 3/2epsilon (say) for epsilon small enough. Algebraist 11:05, 13 May 2008 (UTC)

Revised Proof of Fact II

Algebraist, you are absolutely right. I just said the opposite of what is true. So here is the revised proof.

Proof:Let $\epsilon >0$ be given and then let $\delta =\epsilon /2$.

$x-0<\delta$

$\Rightarrow x<\delta$

$\Rightarrow x<\epsilon /2$

$\Rightarrow 1/x>2/\epsilon$

$\Rightarrow {\frac {1}{x}}-1>{\frac {2}{\epsilon }}-1$

$\Rightarrow [1/x]>{\frac {1}{x}}-1>{\frac {2}{\epsilon }}-1={\frac {2-\epsilon }{\epsilon }}$

$\Rightarrow [1/x]^{-1}<{\frac {\epsilon }{2-\epsilon }}<\epsilon$ because $\forall \epsilon <1$ we have that $2-\epsilon >1$

$\Rightarrow f(x)<\epsilon$

$\Rightarrow f(x)-0<\epsilon$

$\therefore \lim _{x\rightarrow 0^{+}}f(x)=f(0^{+})=f(0)=0$

Fact IV

Here is another thing I thought of. I will try to prove that $2x\geq f(x)\geq x$ for all $x\in [0,1]$.

Proof:
First, let {x}=x-[x] be the fractional part of a real number x.

Now we have that for all $x\in \mathbb {R} ,\exists ![x]$ and $\{x\}$ such that $x=[x]+\{x\}$ and $0\leq \{x\}<1$.

Now let us consider all $y\in \mathbb {R}$ such that $y\geq 1$.

We now have that $y=[y]+\{y\}<[y]+[y]=2[y]$.

$\Rightarrow y<2[y]\Rightarrow y/2<[y]$

$\Rightarrow {\frac {1}{2x}}<[1/x]$ for all $x\in [0,1]$

and using the fact that $[y]\leq y$ for all $y\Rightarrow {\frac {1}{2x}}<[1/x]\leq {\frac {1}{x}}$

$\Rightarrow 2x>[1/x]^{-1}\geq x$

$\Rightarrow 2x>f(x)\geq x$

and then using the squeeze theorem, I can show that the limit of f(x) from the right as x goes to zero is indeed zero and this function is most definitely not unbounded in [0,1]. I think that after these four facts combined, there is no question that f(x) is bounded and Riemann integrable in [0,1].

Fact V

In fact, we can also find the exact value of the integral as follows:

Since, the function as a jump discontinuity at every unit fraction, with 1/2 being the first one from the left as x goes to zero, and in between two consecutive unit fractions, the function is constant

(i.e. $f(x)={\frac {1}{n}}{\text{ for }}x\in \left({\frac {1}{n+1}},{\frac {1}{n}}\right]{\text{ for all }}n\in \mathbb {N}$), we can just find the area underneath the curve by drawing rectangles

with length ${\frac {1}{n}}-{\frac {1}{n+1}}$ with height ${\frac {1}{n}}$ and then add up the areas of all such rectangles.

$\int _{0}^{1}f(x)dx=\sum _{n=1}^{\infty }\left(\left({\frac {1}{n}}-{\frac {1}{n+1}}\right){\frac {1}{n}}\right)=\sum _{n=1}^{\infty }\left({\frac {1}{n^{2}}}-{\frac {1}{n(n+1)}}\right)$

$=\sum _{n=1}^{\infty }{\frac {1}{n^{2}}}-\sum _{n=1}^{\infty }{\frac {1}{n(n+1)}}={\frac {\pi ^{2}}{6}}-\sum _{n=1}^{\infty }\left({\frac {1}{n}}-{\frac {1}{n+1}}\right)={\frac {\pi ^{2}}{6}}-1.$

The first sum is just from the Riemann Zeta function (the values are known) and the second sum is a telescoping series. We can split up the series because it is absolutely convergent. So, what do you guys think? Should I change something or is this enough? Any more stupid mistakes in what I wrote or my reasoning? Come on guys, don't be shy. I just need your input and some constructive criticism.A Real Kaiser (talk) 23:23, 13 May 2008 (UTC)

What purpose are you producing this for? I ask because this will affect the level of detail required in your arguments. For example, if asked to show this function was Riemann integrable, I would say 'clearly increasing and bounded, hence integrable' or possibly 'clearly measurable and almost everywhere continuous, hence integrable', and leave it at that, but I'd expect a bit more if this was set as an exam question or something. Algebraist 11:08, 14 May 2008 (UTC)

(per post on my talk) If this is for convincing a very confused person, I can't guess what might work (the function's bounded above by 1! How can it have infinite integral?). If I was going for full first-year-analysis style all-the-details rigour, though, I would be a bit more careful with V: it's not quite trivial that the Riemann integral has the right limit-related properties to give you that infinite sum. Algebraist 20:47, 14 May 2008 (UTC)

Ummm... Based on the discussion at Algebraist's Talk, it would be enough to prove the integral isn't infinite... Maybe... Using a property of multiplicative inversion that you've been exposed to repeatedly,

$x\in (0,1]\Rightarrow 1/x\in [1,\infty )$

Since we have the basic properties of the floor function: $[u]\leq u\land (\forall v\in [1,2),[v]=1)$ (showing that $[1,\infty )$ is mapped somewhere to its right and then that at least {1} is in the image of that map, so the interval in the next step is best possible), then we get

$\Rightarrow [1/x]\in [1,\infty )$

Using the multiplicative inversion property again:

$\Rightarrow [1/x]^{-1}\in (0,1]$

Now,

$((x=0\Rightarrow f(x)\in \{0\})\land (x\in (0,1]\Rightarrow f(x)\in (0,1]))$

$\Rightarrow (x\in \{0\}\cup (0,1]\Rightarrow f(x)\in \{0\}\cup (0,1])$

and we may simplify this result to

$0\leq f(x)\leq 1,{\mbox{ if }}x\in [0,1]$

Finally we get, for $a,b\in [0,1]$:

$\int _{a}^{b}0\,dx\leq \int _{a}^{b}f(x)\,dx\leq \int _{a}^{b}1\,dx$

(If more detail is needed in that last step, note that any partition of the interval (a,b) produces a Riemann sum for f which is termwise ordered exactly as written.)

With a little computation, we can compute and limit the bounds.

$0=\int _{a}^{b}0\,dx\leq \int _{a}^{b}f(x)\,dx\leq \int _{a}^{b}1\,dx=b-a\leq 1-0=1$

and I don't know how to make its finiteness more transparent. -- Fuzzyeric (talk) 03:41, 18 May 2008 (UTC)

Sum

"Let ABCDEFGH be an eight digit number where A,B,C,D,E,F,G,H are the digits 1,2,3,4,5,6,7,8 in some order. For example, A=4,B=1,C=3,D=2,E=5,F=6,G=7,H=8 gives 41325678. FInd other eight digit numbers in which the three digit number ABC is divisible by 7, the three-digit number BCD is divisible by 6, CDE is divisible by 5, DEF is divisible by 4, EFG is divisible by 3 and FGH is divisible by 2."

I know that E is 5 but don't konw the others. Can someone pls give me some hints as the maths exam is round the corner(to be exact, tomorrow)? tks. —Preceding unsigned comment added by Invisiblebug590 (talk • contribs) 10:26, 13 May 2008 (UTC)

How many other numbers does it want? It looks like there are quite a lot. I suggest starting at the end and working back. FGH being divisible by 2 tells you something about H, but doesn't restrict F or G, for example. You can then work your way up narrowing down your options bit by bit. --Tango (talk) 10:42, 13 May 2008 (UTC)

The "easy" way to solve this is a brute force computer program. You only have 8! = 40320 permutations to evaluate. My program has determined that there are five solutions to your question. Note that BCD, DEF and FGH are all divisible by 2, so that uses up all but one of your even mumbers for D, F & H. BCD and EFG are both divisible by 3, so B+C+D+E+F+G is also divisible by 3. Since the sum 1..8 = 36 then A+H will also be divisible by 3 which reduces the possibilities a lot. -- SGBailey (talk) 11:10, 13 May 2008 (UTC)

If it's any help, the way I found a solution to this was to observe that there are only two choices for F, one of which leads to a unique choice for G. Fixing F and G at these values allows everything else to be worked out without too much difficulty. Algebraist 11:13, 13 May 2008 (UTC)

E=5, DEF is divisible by 4 therefore EF=52 or 56. EFG is divisible by 3 therefore of the div 3s (522, 525, 528, 561, 564, 567) we can try 528, 561, 564, 567. -- SGBailey (talk) 22:22, 13 May 2008 (UTC)

The above was a reply to a comment that got itself deleted, Hence the apparent non-sequitur. -- SGBailey (talk) 22:25, 13 May 2008 (UTC)

The Answer is 73485612. FIgured it out in 15 min. This is how you do it (not very mathematic but it works):

the last 4 digits (EFGH) are even, so H is 2,4,6, or 8. You know in order to use all 8 numbers the last 5 will be every-other even odd even odd even (keep that in mind), so G will be either 1,3,5,or 7. Even next. So depending on what H is, F isnt that. E isthe same but with odd. You start by figuring out the last 4 first because to know the DEF, EF needs to be divisible my 4, and EFG needs to be divisible by 3. so if you make a little chart using this info. you have over 120 possiblities now. Now figure out the EFG set that E is 5, F is even and G makes the sum of the three a multiple of 3. You get 561H, or ABCD561H ( H is 2,4, or 8). Now you have 73248 left to choose from. This part is easier. D will be even, ABC will add to a multiple of 7 and BCD adds to 3 or a maultiple of 3. Looking at this you realize that the only 3 numbers that will give you a multiple of 7 is 734 (14). Now you just eliminated the one that ended with 4. 2 options left. D is 2 or 8. you see what will give you x3. so 7+4+8, 7+3+2, 3+4+8, 7+4+2, 7+3+2, 3+4+2. 348 works. Now you have your answer. A3485612 or 73485612. Its a lot easier to do than to hear.--Xtothe3rd (talk) 01:45, 14 May 2008 (UTC)

As mentioned above, there appear to be 5 answers to the problem, not just the two Xtothe3rd mentions. -- SGBailey (talk) 08:04, 14 May 2008 (UTC)

Unless I've missed the point, 73485612 is invalid as the 3-digit number 734 isn't divisible by 7.…81.159.11.144 (talk) 11:50, 14 May 2008 (UTC)

Yes. Xtothe3rd appears to be under the impression that ABC is a multiple of seven iff A+B+C is a multiple of seven. In fact ABC is a multiple of seven iff 2A+3B+C is a multiple of seven. Algebraist 13:41, 14 May 2008 (UTC)

ABCDEFGH = 23185674, 27385614, 37145286, 41325678, 41385672 I think. -- SGBailey (talk) 10:13, 16 May 2008 (UTC)

Logic circuit design

Please provide symbol/math tags in TeX/HTML for logic gates like NOT, AND, OR, XOR,... Currently, users are uploading image files to depict circuit diagrams. A XML version would be immediately useful beyond Wiki.Anwar (talk) 14:35, 13 May 2008 (UTC)

Feature requests should go to [1], this page is for asking maths questions. --Tango (talk) 18:21, 13 May 2008 (UTC)

Homeless Statistics in China

Hi, I am an academic student currently researching on China's demographic. I am having a difficult time locating the most current information concerning "the homeless percentage in China overall and by region or province and cities vs. rural." I would really appreciate it if anyone can provide me with the most up to date data or point me to the right direction on where to search.

Thank you for your time and help. Your prompt reply will be greatly appreciated.

Sincerely, username: darjeelinguru

Hi. This is really a question for the Humanities Reference Desk. This seems like difficult information to come by. You might start by looking at the page Demographics of the People's Republic of China, which has some related information, but not what you ask for specifically. Then you might look at the references and links at the bottom of that page. Best of luck.

Also, to sign your name automatically, type four tildes in a row (i.e. ~ four times in a row). kfgauss (talk) 18:29, 13 May 2008 (UTC)

We certainly don't make it any easier to choose a reference desk section for such questions by including the ambiguous term "statistics" as a sub-topic for the mathematics section. -- Meni Rosenfeld (talk) 18:40, 13 May 2008 (UTC)

We certainly don't but I think that (a little bit of) common sense goes a long way. Finance and Economics questions should go on the Hum desk but if I had a question on the Black-Scholes model, I'd definitely come here. But I have been here for a while so it would be easier for me to figure out what goes where. Zain Ebrahim (talk) 07:25, 14 May 2008 (UTC)

I would expect China to suppress any statistics on homelessness in their country, and to say "we don't have any homeless people here". If you point out a few of them, they would likely be gone the next day. StuRat (talk) 00:05, 17 May 2008 (UTC)

Mathcad functions

Using the Mathcad statistical functions how would I convert percentile to a z-score and vice versa? 71.100.14.205 (talk) 16:32, 13 May 2008 (UTC)

I don't know what functions Mathcad has built-in, but see error function and (more specifically) probit. --Tardis (talk) 16:03, 14 May 2008 (UTC)

Pi

When was pi first used in England how was it measured? —Preceding unsigned comment added by 82.71.27.169 (talk) 18:26, 13 May 2008 (UTC)

I couldn't be sure, and I am sorry if I am stating the obvious, but have you looked at Pi?

And what precisely do you mean by England?…81.159.11.144 (talk) 11:55, 14 May 2008 (UTC)

I wasn't aware "England" was an ambiguous term... --Tango (talk) 14:24, 14 May 2008 (UTC)

It is when projected back over at least two thousand years of history. Algebraist 15:24, 14 May 2008 (UTC)

Well, he could be referring to England itself, to Britain or the UK generally, or in the English national football team, to which of course the answer is never since their combined IQ isn't likely to get into the double digits. -mattbuck (Talk) 15:26, 14 May 2008 (UTC)

Ah, well that's not a matter of precision, it's a matter of accuracy. "England", "Britain" and "UK" are all different things, there is no ambiguity, just correct and incorrect usage. As for a 2000 year history - I'm not sure Western Europe did much significant maths back then, ideas about Pi probably only reached England a few hundred years ago and the borders have been pretty much fixed for over 1000 years. --Tango (talk) 15:53, 14 May 2008 (UTC)

My point (and it might well be false) was that there were Romans in (what is now) England two millennia ago, Romans tended to drag around Greeks to do any thinking that needed doing, and the Greeks were into geometry. Algebraist 16:06, 14 May 2008 (UTC)

True, there may well have been people using Pi back then. I was thinking of people studying it, which I don't believe anyone in England at that time did (at least not successfully enough to be remembered), since just using it would count as measuring it. --Tango (talk) 20:01, 14 May 2008 (UTC)

It is the case, regrettably, that "England" is often used in a casual, slipshod way by people who mean a wider geographical unit. This seems to cause particular offence to Scots, who are members of a nation, while those in the principality of Wales just add the slight to their general moroseness (it's possible that I am over-generalising here). Not being privy to the OP's reason for wanting to know, it's only a suspicion that he/she actually meant something wider. And of course the Romans reached Scotland and Wales anyway.…81.159.11.144 (talk) 23:19, 14 May 2008 (UTC)

It depends what you mean by "used" and "measured". We know that Archimedes wrote about geometric methods of estimating π and presumably his works were being copied out by at least some scribes somewhere in England in the first millenium - but did they understand what they were copying ? And the masons designing and building Anglo-Saxon churches must have had a working knowledge of the geometry of circles - but does that count as "using" π ? The earliest example I can find of an English mathematician who studied π is John Wallis who discovered the Wallis product in 1655. Gandalf61 (talk) 10:18, 15 May 2008 (UTC)

Numb3rs

An episode of Numb3rs involved a (false) proof for the Riemann hypothesis that was used as a ransom with the intent of breaking encryption. Did they get it mixed up with the P = NP problem, or are they that closely related? — DanielLC 23:33, 13 May 2008 (UTC)

It is suggested that a proof for the Riemann hypothesis may be a key factor in understanding and breaking the pattern of prime numbers, what would in turn speed up our best factorization algorithms of very large numbers. These are frequently used in cryptography for public keys. I guess that's their whole point. — Kieff | Talk 23:42, 13 May 2008 (UTC)

Is the idea that it's still exponential time, but faster than normal, or did they simultaneously (almost) prove that P = NP without even mentioning it? Also, it would have to be something in the way it was proved, or they'd just assume the Riemann hypothesis to be true and then just see if it works. In might not be formal, but if you can break encryptions, who cares. — DanielLC 23:59, 13 May 2008 (UTC)

I think they said something non-specific about the method of the proof giving an easy way to factor numbers. See [2] by Chris Caldwell and the links [3] and [4] in one of the replies. PrimeHunter (talk) 00:07, 14 May 2008 (UTC)

There's no evidence that factoring is NP-complete, and most complexity theorists think it isn't, so factoring being in P doesn't imply P=NP. I don't think it would even affect most theorists' faith in P≠NP very much; factoring is considered much easier than known NP-complete problems (though a polytime algorithm would still be very surprising). -- BenRG (talk) 01:06, 14 May 2008 (UTC)

P=NP doesn't have that much to do with practical ease of breaking encryption. In particular, being in P doesn't mean a problem is easy. Even a modest-looking polynomial like $n^{20}$ is more difficult in practice than an exponential like $2^{n}$. And it is believed that, if a proof for P=NP is found, it will involve huge polynomials, with degrees which could easily surpass millions. So even if the Riemann hypothesis is related to easier breaking of factorization-based systems, it doesn't mean it is in any way related to P=NP. -- Meni Rosenfeld (talk) 08:31, 14 May 2008 (UTC)