Wikipedia:Reference desk/Mathematics

Welcome to the mathematics section
of the Wikipedia reference desk.

skip to bottom

Select a section:

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

Want a faster answer?

Main page: Help searching Wikipedia

   

How can I get my question answered?

• Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
• Post your question to only one section, providing a short header that gives the topic of your question.
• Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
• Don't post personal contact information – it will be removed. Any answers will be provided here.
• Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
• Note:
  • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
  • We don't answer requests for opinions, predictions or debate.
  • We don't do your homework for you, though we'll help you past the stuck point.
  • We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

Ready? Ask a new question!

How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

• The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.

See also:

• Teahouse
• Help desk
• Village pump
• Help manual

May 31

Notational Inconsistencies in Vectors

I'm confused about the use of $|$ in notations for the length of a vector. According to the Dot product article:

$|\mathbf {a} |={\sqrt {\mathbf {a} \cdot \mathbf {a} }}$

However, the Norm_(mathematics)#Euclidean_norm article writes:

$\|\mathbf {x} \|:={\sqrt {x_{1}^{2}+\cdots +x_{n}^{2}}}$

So my question is in a couple of parts:

1. Is there a difference between ||a|| and |a|? Is one using the wrong notation?
2. If not, what's the difference between the two?

• The dot product article says: a.a is the square of the length of a (which is written as ||a|| on the Norm article).
• This implies that:

$|\mathbf {a} |={\sqrt {\|\mathbf {a} \|^{2}}}$

which would imply that ||a|| and |a| are the same.

Thanks in advance --Philipwhiuk (talk) 12:22, 31 May 2010 (UTC)

There's no real difference between the two, it's just a different notation for the same thing. Some people reserve |x| for (real or complex) absolute value and denote more general norms with ||x||, some don't bother and use the simpler |x| for all norms.—Emil J. 12:36, 31 May 2010 (UTC)

Many thanks for your quick reply EmilJ. --Philipwhiuk (talk) 12:39, 31 May 2010 (UTC)

... and, of course, $|\mathbf {a} |={\sqrt {\mathbf {a} \cdot \mathbf {a} }}={\sqrt {a_{x}^{2}+a_{y}^{2}+a_{z}^{2}}}$ for a 3-D vector $\mathbf {a}$. Dbfirs 16:38, 31 May 2010 (UTC)

Percentage increase

if I have four things, and I add another thing, is that usually called a 25% increase in things (a percentage of the original amount) or a 20% increase (a percentage of the final amount)? 81.131.69.251 (talk) 18:47, 31 May 2010 (UTC)

The former, i.e. a 25% increase. —Qwfp (talk) 18:51, 31 May 2010 (UTC)

Ta. 81.131.69.251 (talk) 18:53, 31 May 2010 (UTC)

Please help with a couple questions I've been stuck on for weeks! Curvature, projective modules & metric spaces

Hey everyone, I'm revising for my exams (hooray) at the moment, and having arduously completed about 10 years of past papers, I've been left with about 4 or 5 questions which I just can not for the life of me finish. I know you're meant to post all your working etc. here but as I said, these are the only questions left I can't get my head around, so there's very little working I've managed to achieve or else I would probably have been able to finish the problem with enough perseverance.

I appreciate I'm asking a for lot of help, so if you just have even 1 suggestion for any of these problems which could be of use then please do shout, the more of these I can get sorted before tomorrow the better, and of course I don't expect you to have to go out of your way to pick up my slack when I can't figure something out! :)

1. (Final part of a long question) Show that a finitely generated projective module over a principal ideal domain is free. I've shown that every free module over an arbitrary ring is projective, where here I'm using the definition that an R-module p is projective if whenever we have module homomorphisms $f:M\to N$ and $g:P\to N$, with f surjective, there exists a homomorphism $h:P->M$ with $f\circ h=g$.

2. Let (X,d) be a metric space with at least 2 points. If $f:X\to \mathbb {R}$ is a function, we define Lip(f) $Lip(f)\,=\,sup_{x\neq y}{\frac {|f(x)-f(y)|}{d(x,y)}}+sup_{z}|f(z)|$, provided this supremum is defined. Now with $X=\mathbb {R}$, suppose $(f_{i})_{i=1}^{\infty }$ is a sequence of functions with $Lip(f_{i})\leq 1$ and with the property $f_{i}(q)$ converges as i tends to infinity, for every rational q. Show the $f_{i}$ converge pointwise to a function f satisfying $Lip(f)\leq 1$. Suppose also $(f_{i})_{i=1}^{\infty }$ are any functions with $Lip(f_{i})\leq 1$. Show there is a subsequence $f_{i_{1}},\,f_{i_{2}},...$ which converges pointwise to a function f with $Lip(f_{i})\leq 1$. Where to start? I showed that Lip(X) is a vector space over $\mathbb {R}$ and that Lip is a norm on it, and then from then on I have no clue where to go. I tried to work out how to treat the irrational numbers in the first part and I presume it utilizes the density of the rationals, but I haven't been able to get anywhere at all from there - it was a hard year for Analysis and this was definitely the worst question, completely off the course.

3. Deduce (from the fact that the Gaussian curvature K of a surface locally given by the graph of an infinitely differentiable function $f:U\to \mathbb {R}$, where U is an open subset of $\mathbb {R} ^{2}$, is equal to $K={\frac {f_{xx}f_{yy}-f_{xy}^{2}}{(1+f_{x}^{2}+f_{y}^{2})^{2}}}$ - this was the first part of the question, so this is assuming I calculated that right!) that if $\Sigma \subset \mathbb {R} ^{3}$ is a compact surface without boundary, its curvature is not everywhere negative. Give with justification a compact surface in $\mathbb {R} ^{3}$ without boundary whose Gaussian curvature must change sign. I can see that the curvature is negative if and only if the second fundamental form is negative, but I'm not sure if they're looking for a geometrical argument here or an algebraic one - personally I'd prefer the latter if it really is a 'deduce' and not a 'show'. In addition, perhaps I'm getting confused, but I thought a compact surface had to be closed and bounded, in which case surely it necessarily has a boundary? I don't think I can do the last part without understanding what they mean by 'without boundary' - could we just for example attach a hemisphere to part of a hyperboloid (in a sortof 'icecream cone' fashion) to get a surface with both positive and negative curvature, or is there more to it than that?

As above, I'm sorry this post is so long and wordy, but I've spent weeks and weeks doing past papers and I've whittled it down to just these questions to ask for help on, so if you can suggest anything in any case which might be of use in any of the 3 questions please don't hesitate, even if you only have time for a quick comment. I would say that questions 2 and 3 are probably the most pressing, since I was able to tackle the majority of Q1 without any problems. Thankyou so so much in advance! :-) Otherlobby17 (talk) 18:49, 31 May 2010 (UTC)

I think I have some suggestions for part 2 of question 2 Suppose also $(f_{i})_{i=1}^{\infty }$ are any functions with $Lip(f_{i})\leq 1$. Show there is a subsequence $f_{i_{1}},\,f_{i_{2}},...$ which converges pointwise to a function f with $Lip(f_{i})\leq 1$. We just need to find a subsequence that converges for all rationals then use the first part. All the fi must have values within [-1,1] since their Lip is less than 1. By the Tychonoff theorem, [-1,1]^(omega) is compact; it's also first countable so it's sequentially compact. Now enumerate the rationals in the real numbers as q1,q2,q3... And write out the q1,q2,q3... horizontally and the f1,f2,f3... vertically like a multiplication table, and then evaluate each fi at qj.

Then this is a sequence of sequences in [-1,1]^(omega) (the rows are the elements of [-1,1]^(omega)), and so has a convergent subsequence. This subsequence is the one you want. I might be wrong I’m only a student. I think user:pma has expertise in this area Money is tight (talk) 04:16, 1 June 2010 (UTC)

For 1), you probably know the structure theorem for finitely generated modules over a PID. It shows that any finitely-generated torsion-free module over a PID is free. Now, over any ring, a projective module is a direct factor of some free module. (Find a surjection from a free module onto it and then split it.) Since a submodule of a free (and hence torsion-free) module is torsion-free, we're done.

Actually, though, you don't need finitely-generated. That's because there's a theorem (using Zorn's lemma) that says that a submodule of a free module over a PID is free. 70.51.11.224 (talk) 05:16, 6 June 2010 (UTC)

For 2), take a real number r and show that f_i(r) is a Cauchy sequence. Take some q close to r. For large i, the terms f_i(q) will be within a of each other. Then by the Lipschitz condition on f_i, the terms f_i(r) will be within 2|r-q| + a of each other. You can make this smaller than any epsilon you pick, by a suitable choice of q and then a. So f_i(r) is Cauchy. I imagine the fact that the limit function has norm <= 1 can be proved by some passage to the limit, but I haven't looked at it in detail.

For the second part of 2, the point is to find a subsequence satisfying the above condition. Enumerate the rational numbers q_1, q_2, etc. Since the sequence f_i(q_1) is bounded by 1, you can pick a convergent subsequence. Within that subsequence of the f_i, pick a subsequence such that f_i(q_2) converges. And so on. Now you have a sequence of nested subsequences. Extract a single subsequence from that by a diagonal construction. This subsequence will be such that f_i(q) converges for all rational q. 70.51.11.224 (talk) 05:35, 6 June 2010 (UTC)

By the way, it looks like the last part of 2 can also be deduced from the Banach-Alaoglu theorem. 70.51.11.224 (talk) 05:40, 6 June 2010 (UTC)

June 1

Find extremum

I remember from calculus (a looongg time ago ;) that to find if a point is an extremum of a function you take increasinly higher order derivatives until the result is a nonzero constant. I've come across this again, but I'm stuck. How do you do that with something like sin(2x)? That will never differentiate to a constant! Of course I know that from the basic properties of the sin function that the extrema are at 45, 135, etc., etc. in my example, but the problem I have to deal with may be much more complex than that.

The higher order derivatives don't have to be a nonzero constant. They just need to have a nonzero value at the point you are evaluating. For $\sin(2x)$ at $x_{0}=\pi /4$, differentiating once gives $2\cos(2x_{0})=0$; once more gives $-4\sin(2x_{0})=-4<0$, so this is a local maximum. -- Meni Rosenfeld (talk) 18:33, 1 June 2010 (UTC)

Our article is here: higher-order derivative test.—Emil J. 18:36, 1 June 2010 (UTC)

Crop circles of pi and Euler's identity

How does this crop circle work? Kittybrewster ☎ 20:00, 1 June 2010 (UTC)

What crop circle? -- Meni Rosenfeld (talk) 20:46, 1 June 2010 (UTC)

As shown in google search +crop circle +eulers identity Kittybrewster ☎ 21:26, 1 June 2010 (UTC)

explanation here [1]. why are aliens communicating in ASCII and not Unicode ? 87.102.77.88 (talk) 23:17, 1 June 2010 (UTC)

Thank you. Very comprehensive response. Kittybrewster ☎ 05:05, 2 June 2010 (UTC)

As shown in google search +crop circle +pi +2008 +Wroughton. Kittybrewster ☎ 05:05, 2 June 2010 (UTC)

Found it. Kittybrewster ☎ 15:00, 3 June 2010 (UTC)

Maximum/Minimum Irradiance for "Human habitable" planet temperatures?

(Third time's a charm)
I keep trying to create a simple model for anyone who wants to speculate on a planet having
habitable temperatures for people (not extremophiles) based on Irradiance.
Take for example HD 38801 b:
Star Radius = 2.53 sol
Star Te = 5222 K
Stefan–Boltzmann constant, σ = 5.67051E-8
Semi-major axis = d, in this case 1.7
Eccentricity = e, in this case 0
Emissivity = ε, (Earth=0.62009)
Albedo = A, (Earth=0.3)

=((((R^2)*σ*(Te^4)*(1-A))/(4*ε*(d±(d*e))^2))^0.25)-273.15
So I can get a global annual average temperature for a planet,
If I assume a global average albedo and a global average emissivity

	Albedo
εmissivity	0.20	0.25	0.30	0.35	0.40	0.45
0.80	5°C	1°C	-4°C	-9°C	-14°C	-20°C
0.75	10°C	5°C	0.7°C	-4°C	-10°C	-15°C
0.70	15°C	10°C	5°C	0.3°C	-5°C	-10°C
0.65	20°C	16°C	11°C	5°C	-0.1°C	-6°C
0.60	26°C	21°C	16°C	11°C	5°C	0.5°C
0.55	33°C	28°C	23°C	17°C	11°C	5.4°C

Ignoring the perspective that single value Albedo and Emissivity are very
simplistic, since "Global Annual Average Temperature" is also but it exists:
A) at what levels of irradiance (max/min) does this become moot?
B) what combinations of Albedo & Emissivity are unrealistic or possible??

Just to be clear I am talking about people. The GAAT (14°C) is a surface temperature.24.78.167.139 (talk) 20:45, 1 June 2010 (UTC)

I came upon this chart in a search and realized this illustrates well the idea that there are a lot of possibilities but some are unrealistic. - 24.78.167.139 (talk) 20:45, 1 June 2010 (UTC)

This isn't really the right forum for that question. We cover mathematical physics but this seems more like general science or astronomy.--RDBury (talk) 00:45, 2 June 2010 (UTC)

"Astrophysics (...) is the branch of astronomy that deals with the physics of the universe, ..." 24.78.167.139 (talk) 03:33, 2 June 2010 (UTC)

Note that planets and moons are heated by many factors other than the light of their suns:

1) Tidal forces between planets, moons, and suns. Most significant if you are nearby a large body.

2) Residual heat from initial formation. This dissipates quickly for small bodies, but lasts for billions of years on larger planets.

3) Radioactive decay (fission).

4) Nuclear fusion. Only a factor on the largest planets, which are essentially "failed stars".

5) Bombardment by meteors, comets, solar wind, etc.

While we tend to think of solar heating as the most significant heat source, this is only true for the surfaces of planets near the host star. However, it's quite possible for there to be other scenarios where the heat is mostly provided by different sources, such as a moon around a massive planet far from it's sun. StuRat (talk) 04:17, 3 June 2010 (UTC)

Regardless of whether solar heating is the most significant or not that is my question, I am not asking about "other scenarios," I am asking about solar heating! Why do you people always have to change the question so that you can lecture on what makes you feel important to express?? 24.78.176.110 (talk) 08:56, 11 June 2010 (UTC)

There may be ice on Mercury. Dmcq (talk) 07:38, 3 June 2010 (UTC)

• "The mean surface temperature of Mercury is 442.5 K" (169.35°C), and it has almost no atmosphere, so these are weird responses considering I mention I was referring to "habitable (surface) temperatures" for people.
• Scientists and journalists are willing to speculate wildly that there may be life on this or that extrasolar planet, so it isn't all that odd to look at an extrasolar planet or moon as having habitable temperatures for people. I don't understand the lack of imagination on that possibility. 24.78.167.139 (talk) 20:35, 3 June 2010 (UTC)

As I said before the mean temperature is quite a bad guide to whether there are places where people could live. There are places on Mercury where there may be a quite reasonable temperature for people though you'd have to move around. For Venus floating around in a balloon might give a reasonable habitable temperature even though the surface temperature is hotter than the mean Mercury temperature. I don't see why that is lack of imagination. Dmcq (talk) 21:49, 3 June 2010 (UTC)

You seem to be unable to hear what I am asking over the importance of your opinion; I have not asked for the bad possibilities I have asked for the good ones. Venus is not considered in the habitable zone for a reason, it is ludicrous for you to suggest that Mercury is in the habitable zone.

• I repeat: Global Annual Average Surface Temperature:
  

A) at what levels of irradiance (max/min) does this become moot?
B) what combinations of Albedo & Emissivity are unrealistic or possible??
Anyone? - 24.78.176.110 (talk) 08:56, 11 June 2010 (UTC)

June 2

weakly normalised

In some articles like this there are some assumptions that a function need to be weakly normalised. I didn't found any explanation for this. What it is mean? (This is not about something of Lambda calculus) --77.124.146.172 (talk) 05:34, 2 June 2010 (UTC)

closed immersion of smooth varieties

If X, Y are smooth varieties and f: X -> Y is a closed immersion, is f(X) smooth? In Liu, it is proved that it is a regular immersion, so the answer seems to be "no", but what is a counterexample? Ringspectrum (talk) 17:12, 2 June 2010 (UTC)

June 3

Tangent/secant functions

Who discovered the tangent and secant functions? According to the article Trigonometric functions#History, it is Muhammad ibn Mūsā al-Khwārizmī and Abū al-Wafā' Būzjānī, respectively; according to the article Thomas Fincke, it is Thomas Fincke. Which is correct here? I try to ask here to clear up the discrepancies and to be able to correct the articles in question. Iceblock (talk) 04:53, 3 June 2010 (UTC)

Much mathematics was known to eastern scholars long before it was formally introduced to western civilisation. I suspect that this is true of these functions, though I don't know whether Thomas Fincke independently discovered the functions or just published the knowledge. Perhaps someone has access to his publication? I think he probably just introduced the words (and abbreviations). They were formerly known as "umbra versa" & "umbra recta", translations into Latin of the Arabic "tables of shadows" which were, in turn, developments of work by Indian mathematicians. Our article History of trigonometry has more detail of the development. Dbfirs 06:24, 3 June 2010 (UTC)

It's not a huge mystery, the Thomas Fincke article says that he 'introduced' secant and tangent but what that means is he introduced the terms, not that he invented or discovered the functions. The article should be rephrased to avoid confusion but it's not a discrepancy.--RDBury (talk) 06:49, 3 June 2010 (UTC)

Yes, just the terms. Regiomontanus had prevoiusly published a table of tangents in the west. I'll make the adjustment to the article if no-one else has done so. Dbfirs 06:57, 3 June 2010 (UTC)

Thank you very much, both of you! Iceblock (talk) 07:26, 3 June 2010 (UTC)

What is the name?

Is there a name for $\scriptstyle {\frac {a-b}{a+b}}$ when $\scriptstyle a>b>0$ ? Bo Jacoby (talk) 16:09, 3 June 2010 (UTC).

It does come up often but I haven't seen a name. Half the relative difference would be one name - but there's all sorts of definitions of relative difference. You might also like to look at the law of tangents Dmcq (talk) 19:56, 3 June 2010 (UTC)

Is there a name for the ratio $\scriptstyle {\frac {\sigma }{\mu }}$ between the standard deviation and the arithmetic mean? That would also solve the first problem. Bo Jacoby (talk) 09:28, 4 June 2010 (UTC).

Coefficient of variation. I don't see how that solves the first problem though. --Qwfp (talk) 10:26, 4 June 2010 (UTC)

Thank you very much! Just what I needed. If a population contains only two numbers, $\scriptstyle a>b$, then the mean value is $\scriptstyle \mu ={\frac {a+b}{2}}$ and the standard deviation is $\scriptstyle \sigma ={\sqrt {\frac {(a-\mu )^{2}+(b-\mu )^{2}}{2}}}={\sqrt {\frac {\left(a-{\frac {a+b}{2}}\right)^{2}+\left(b-{\frac {a+b}{2}}\right)^{2}}{2}}}={\sqrt {\frac {\left({\frac {a-b}{2}}\right)^{2}+\left({\frac {-a+b}{2}}\right)^{2}}{2}}}={\sqrt {\frac {2\left({\frac {a-b}{2}}\right)^{2}}{2}}}={\sqrt {\left({\frac {a-b}{2}}\right)^{2}}}={\frac {a-b}{2}}$, so the coefficient of variation is $\scriptstyle {\frac {\sigma }{\mu }}={\frac {\frac {a-b}{2}}{\frac {a+b}{2}}}={\frac {a-b}{a+b}}.$ Bo Jacoby (talk) 08:25, 5 June 2010 (UTC).

That's quite a long derivation for σ. It's obvious that the absolute deviation from the mean is ${\tfrac {a-b}{2}}$ for both points, so σ, the rms of the deviation, is also ${\tfrac {a-b}{2}}$. -- Meni Rosenfeld (talk) 20:03, 5 June 2010 (UTC)

True. But when Qwpf says: I don't see how that solves the first problem it is perhaps not helpful to answer that it's obvious. Obviousness is subjective. Note also that the absolute deviation does not enter into the derivation. Only the square of the signed deviation enters. Bo Jacoby (talk) 23:54, 5 June 2010 (UTC).

Integrating

I'm trying to integrate 1/(x-x^2), but can't remember which method to use. I considered u-substitution and integ. by parts, but they don't work. Please advise. —Preceding unsigned comment added by 142.58.43.148 (talk) 21:33, 3 June 2010 (UTC)

Have a look at partial fractions and partial fractions in integration Dmcq (talk) 21:56, 3 June 2010 (UTC)

$\int {\frac {1}{x-x^{2}}}dx=\ln \left|x-x^{2}\right|+C$. 76.199.147.211 (talk) 22:01, 3 June 2010 (UTC)

'fraid not. 1/(x-x^2) turned into partial fractions is

${\frac {1}{x-x^{2}}}={\frac {1}{x}}+{\frac {1}{1-x}}$

You get a minus on the second term when you integrate it. Dmcq (talk) 22:12, 3 June 2010 (UTC)

It can also be done by u-substitution, try $u={\frac {1-x}{x}}.$ Martlet1215 (talk) 16:10, 4 June 2010 (UTC)

You'd have to already know the answer before you'd think of using that transformation! I think the usual term for that is 'magic'. Dmcq (talk) 19:32, 4 June 2010 (UTC)

June 4

Finding angle between vectors in two dimensions

How would you find the angle between two vectors in the coordinate plane, given their endpoint and assuming they start at the origin, WITHOUT using the dot product or similar (a.k.a. advanced) properties. An equation using the coordinates would be nice! dude❶❽❶❽ (talk) 01:06, 4 June 2010 (UTC)

You should see that there are always two angles between any two vectors in the conditions you describe. Let's deal with the smallest one (which we'll call angle BAC), since witht that you can easily find the bigger one. If you know the two vectors' start and endpoints, then you also know their lengths (call them AB and AC, A being (0,0)). Use the distance formula to find the distance between the vectors' endpoints (BC). Then use the Law of Cosines to find the angle: $BC^{2}=AB^{2}+AC^{2}-2(AB)(AC)(\cos m\angle BAC)$. Elementary mathematics. 76.199.147.211 (talk) 02:12, 4 June 2010 (UTC)

TO simplify even further $m\angle BAC=\arccos {\frac {BC^{2}-AB^{2}-AC^{2}}{-2(AB)(AC)}}$

Oh yeah. That was dumb of me, I recently learned Law of Cos. Thank you! dude❶❽❶❽ (talk) 02:38, 4 June 2010 (UTC)

But, of course, the cosine rule is really the dot product in disguise, since

$AB^{2}+AC^{2}-BC^{2}=(B_{1}^{2}+B_{2}^{2})+(C_{1}^{2}+C_{2}^{2})-((C_{1}-B_{1})^{2}+(C_{2}-B_{2})^{2})=2(B_{1}C_{1}+B_{2}C_{2})=2{\overrightarrow {AB}}.{\overrightarrow {AC}}$ Gandalf61 (talk) 16:32, 5 June 2010 (UTC)

Co-NP

On our Co-NP page it says that the complemenet to subset sum is, "Does every subset sum to a nonzero number?" Wouldn't a yes/no answer to this imply a no/yes answer to "Does there exist a subset that sums to zero?"? If so, then why is subset sum not equivalent to its complement since an algorithm solving one solves the other? 66.202.66.78 (talk) 07:26, 4 June 2010 (UTC)

The difference is in the asymmetry between "yes" and "no" in the definition of NP. A problem is in NP if "yes" answers have a proof that can be verified quickly - there's no similar requirement for "no" answers. For "Does every subset sum to a nonzero number?", it is not known that a positive answer can be easily verified, so it's not known to be in NP. But a negative answer, accompanied with a counterexample, can be trivially verified - so it's in co-NP.

You are correct that if a deterministic polynomial-time algorithm solves an NP-complete problem, then it trivially also solves its complement, so in this case P = NP = co-NP. But if P ≠ NP then also P ≠ co-NP and possibly NP ≠ co-NP. -- Meni Rosenfeld (talk) 07:42, 4 June 2010 (UTC)

I understand that if we had a polytime algorithm to solve subset sum, then NP = co-NP; what I meant was that since we can reduce any algorithm solving subset sum to one solving the above descion problem in polytime, why doesn't this imply NP = co-NP? In other words, let A be any algorithim solving subset sum and let B flip yes to no and no to yes, doesn't running B on the output of A solve co-Subset Sum, and if so, why doesn't this imply NP = co-NP? 66.202.66.78 (talk) 08:05, 4 June 2010 (UTC)

I thought co-NP = NP implied P = NP?66.202.66.78 (talk) 08:06, 4 June 2010 (UTC)

Since the word solving here seems unlcear, when I say an algorithm solving subset sum, I am talking about any algorithm, not just polytime ones:) 66.202.66.78 (talk) 08:12, 4 June 2010 (UTC)

Last edit to this rush of edits, I swear. I was wrong about the co-NP = NP implies P = NP; sorry. 66.202.66.78 (talk) 08:16, 4 June 2010 (UTC)

[ec] Because "an algorithm solving subset sum" has nothing to do with it being in NP. Subset-sum is in NP because instances which have a positive answer also have a certificate which can be polynomially verified.

Presumably, P ≠ NP and NP ≠ co-NP. In this case:

• Solving a subset-sum instance requires super-polynomial time in the worst case - it is not in P.
• Solving co-subsetsum instance requires super-polynomial time in the worst case - it is not in P.
• If the answer to an instance of subset-sum is "yes", then there is a certificate (a subset with a sum of 0) that, once we have it, anyone can polynomially verify that the answer is indeed "yes". It is in NP.
• There are instances of subset-sum for which the answer is "no", and there is no certificate that can be used to easily verify it. It is not in co-NP.
• If the answer to an instance of co-subsetsum is "no", then there is a certificate (a subset with a sum of 0) that, once we have it, anyone can polynomially verify that the answer is indeed "no". It is in co-NP.
• There are instances of co-subsetsum for which the answer is "yes", and there is no certificate that can be used to easily verify it. It is not in NP.

To the best of my knowledge, co-NP = NP does not imply P=NP. The converse is true, though. -- Meni Rosenfeld (talk) 08:28, 4 June 2010 (UTC)

I see, for some reason I was thinking that X and Y are two decison problems and A and algorithm solving both of them, then they were both equal; so, even if the same algorithm(flipping yes and no) solves subsum and cosubsum, they are still different. I'm not sure why I was thinking what I was, thank you:) 66.202.66.78 (talk) 09:00, 4 June 2010 (UTC)

The most common notion of reduction in this area, used in the definition of NP-completeness for instance, is polynomial-time many-one reduction (aka Karp reduction). Subset sum is not many-one reducible to its complement (unless NP = coNP). The idea of flipping the yes/no outcome of an algorithm only gives a polynomial-time Turing reduction (aka Cook reduction), or better, a tt-reduction. Unlike many-one reduction, NP is not closed under tt- or Turing-reductions (unless NP = coNP, again).—Emil J. 10:10, 4 June 2010 (UTC)

Drawing a quadrilateral?

I have been given 4 side lengths- 9, 10, 11 and 12 cm.

Is there a way to calculate the maximum are bound by these dimensions?

I must create a polygon with the maximum area, inscribed in a circle. Are the two the same (ie. does a polygon with given side lengths have maximum area when each vertex touches a point in a circle)?

Is there a program I can use to help me with this? The shape must be drawn within an accuracy of one-tenth of a millimeter.

Thanks in advance!

-PerfectProposal 14:31, 4 June 2010 (UTC)

I can totally help with this - see Brahmagupta's formula - it should be exactly what you're looking for, along with the further material linked at the end. SamuelRiv (talk) 17:44, 4 June 2010 (UTC)

The Brahmagupta's formula article doesn't say, however, whether a quadrilateral inscribed in a circle is the maximum possible area for any arrangement of four sides. It might be, but I am not sure.

My intuition says that the arrangement of four sides that yields the largest circle that can be inscribed within the quadrilateral, would correspond to the largest area quadrilateral.

I can think of iterative methods to do this too. Connect the four sides, then adjust the vertex angle of one side (which will control all the other corner angles) until a maximum area is found. Repeat for a different arrangement of sides and then pick the largest area. ~Amatulić (talk) 18:35, 4 June 2010 (UTC)

Brahmagupta's formula#Extension to non-cyclic quadrilaterals : "It follows from this fact that the area of a cyclic quadrilateral is the maximum possible area for any quadrilateral with the given side lengths." Maybe the article should say that earlier on? --Qwfp (talk) 19:17, 4 June 2010 (UTC)

Ah, thanks, I missed that sentence. ~Amatulić (talk) 19:37, 4 June 2010 (UTC)

That's excellent- thanks. Is there a piece of software I can use to assist me in drawing the cyclic quadrilateral? I imagine it'd be rather difficult to draw by hand with that level of accuracy. PerfectProposal 14:18, 5 June 2010 (UTC)

Can I get GeoGebra to do it for me? I've made a quadrilateral, but can I ask it to make a cyclic quadrilateral, without trial and error? PerfectProposal 16:38, 5 June 2010 (UTC)

Quadrilateral 2d shape

Hello. The shape produced by subtracting a rectangle from within another rectangle (eg the outer perimeter but not of zero thickness) - I need to write a technical description and am having trouble describing this shape - does it have a name? Thanks.87.102.32.39 (talk) 23:04, 4 June 2010 (UTC)

Well, the equivalent with circles is called an annulus. I've never heard of a name for it with rectangles. You could call it a "rectangular annulus", I suppose, and people would probably understand (you should still include a definition, or at least a picture). One issue that comes up with rectangles but not circles is orientation - are the sides of the inner rectangle parallel to the sides of the outer one? That might affect the name, if there is one. --Tango (talk) 02:16, 5 June 2010 (UTC)

Yes parallel (and the centres coincident) (like a window frame).87.102.32.39 (talk) 02:19, 5 June 2010 (UTC)

Try 'rectangular border of thickness t and external dimensions x by y'. -- SGBailey (talk) 05:10, 5 June 2010 (UTC)

Why not call it a frame then ? Bo Jacoby (talk) 07:47, 5 June 2010 (UTC).

I suppose I could.87.102.32.39 (talk) 10:43, 5 June 2010 (UTC)

I will use rectangular frame that seems non ambiguous. Thanks.

87.102.43.94 (talk) 15:39, 5 June 2010 (UTC)

Resolved

June 5

General statistics question

Consider a function $f$. Suppose you perform a series of experiments with several values of $x$, and record the values for $f(x)$. Is there a way to derive from this information an approximation for the function $f$?--Wikinv (talk) 13:05, 5 June 2010 (UTC)

Yes, lots of ways. Which you would use depends on what kind of function you are expecting (linear? quadratic? a higher degree polynomial? exponential? logarithmic?). What kind of function you should expect will depend on what the function represents. You can't work out what to expect just by looking at the values you have - for example, if you have n points you will definitely be able to find an nth degree polynomial that is a perfect fit, but it would be pure luck if that was right, since it depends on how many points you measured, which is arbitrary. It also depends on whether the values for f(x) that you record are exact or have some error to them. So, in short, you need to give us more information about what you are trying to do. --Tango (talk) 13:19, 5 June 2010 (UTC)

Curve fitting covers this briefly. It helps if you have some expectation or a priori knowledge of what the shape is going to be. If not plotting the curve and looking at it is a good place to start - then you can see if it is straight, curving upwards or downwards, oscillating, hump shaped and tending to a particular value at extremities etc - the shape of the curve helps youchoose where to start with the curve fitting equations.87.102.43.94 (talk) 15:45, 5 June 2010 (UTC)

If there are no errors in the measurements of f, then cubic splines is a popular method for interpolation. If you're trying to find the function f exactly, assuming it has some simple form, it can be tricky - but often can be done by applying various transformations to the values until you come up with something recognizable.

If there are errors, and to compensate you have relatively many observations, one typically uses some form of least squares fitting. Nonparametric regression is an approach that assumes as little as possible - Kernel regression is its staple method. -- Meni Rosenfeld (talk) 18:07, 5 June 2010 (UTC)

Symmetry in a multi-dimensional space

Are the points (1,2,3,4), (1,3,2,4) symmetric in a four-dimensional space (or in any multi-dimensional space, in which the vectors are embedded)? i.e. can either vector be obtained from the other one by translation, reflection and/or rotation in a four- (or multi-) dimensional space? HOOTmag (talk) 18:15, 5 June 2010 (UTC)

The sequences you describe are 1 dimensional (you definately didn't mean two points in four or more dimensions ?) - in a normal eg euclidean 1d space there's no way to do it, the only way I can think of is to define a sort of 'fracture plane' ie boundary in thee number line to do, (or even more complicated non-uniform descriptions).87.102.43.94 (talk) 18:42, 5 June 2010 (UTC)

Yes, I really meant a point in a four dimensional space. HOOTmag (talk) 19:00, 5 June 2010 (UTC)

Yes, one point is a reflection of the other. -- Meni Rosenfeld (talk) 19:05, 5 June 2010 (UTC)

Do all permutations - of a given sequence (point) of n-dimensional space - constitute reflections of each other, in that space? HOOTmag (talk) 19:21, 5 June 2010 (UTC)

Well, yes, but any two points P and Q in n-dimensional space are symmetric under reflection in the n-1 dimensional space that is perpendicular to the line between P and Q and contains the mid-point of PQ. Gandalf61 (talk) 19:30, 5 June 2010 (UTC)

Thanx much. HOOTmag (talk) 10:12, 6 June 2010 (UTC)

niggle. if it's a (Euclidean vector) vector and not a point then the transformation isn't possible (using the 3 transformations above) if the magnitudes are not the same, (?) I suppose point were meant. Think I'm getting lines and vectors mixed up. Ignore me.87.102.43.94 (talk) 20:18, 5 June 2010 (UTC)

Anyways, thank you for your response. HOOTmag (talk) 10:12, 6 June 2010 (UTC)

Well, you can translate one vector by the difference between the two and get the other vector... that's true in any dimension... --Tango (talk) 19:12, 5 June 2010 (UTC)

Of course. I had to omit the option of translation... HOOTmag (talk) 19:21, 5 June 2010 (UTC)

Any permutation of the vector components will have the same norm, so they're all rotationally symmetric in any direction. Within permutations of a vector alone, however, one can analyze it in terms of a permutation group, which has some fun properties and is usually used as an introduction to group theory. The actual rotation group for all reals in 4D, though is SO(4), which is a group that comes in handy in physics (well, in 3d it does). SamuelRiv (talk) 19:31, 5 June 2010 (UTC)

Thanks a lot. HOOTmag (talk) 10:12, 6 June 2010 (UTC)

Any two points in 4-dimensional Euclidean space are reflections of each other if you suitably position the "mirror". Just make it a 3-dimensional affine subspace that is the perpendicular bisector of the line segment between the two points.

The permutohedron of order 4

But if you're interested in permuting the four Cartesian coordinates, then here's what happens: there are 24 permutations. All of them have the same sum of four coordinates; therefore all of them lie in a common 3-dimensional affine subspace. Since they lie in a common 3-dimensional Euclidean space, one can draw a picture of the polyhedron whose vertices they are. It's a polyhedron with 24 vertices, 36 edges, and 14 faces. If you feel that Greek-derived names make something sound hifalutin and scientific, it's sometimes called a tetrakaidekahedron because it has 14 faces. And sometimes it's called a permutohedron because of the way it's derived from permutations as described above. Michael Hardy (talk) 00:27, 6 June 2010 (UTC)

Oh, that's wonderful! Thank you! HOOTmag (talk) 10:12, 6 June 2010 (UTC)

June 6

Operator, or transform, as a mapping between classes of functions

Let's use the term "operator", or "transform", for a mapping (whether explicit or implicit) between classes sets of functions. Is there any common term for an operator/transform which is induced by a first-order formula, containing logical symbols only - except for function-symbols for substituting functions which are mapped to one another by that operator/transform? HOOTmag (talk) 11:17, 6 June 2010 (UTC)

You might mean sets instead of classes, working with classes can be awkward and functions are normally defined in terms of sets. In logic you do get classes. A function may have a set of functions as its domain or co-domain. Substituting into a logical formula is also called instantiation. If you are preserving some structure by your mapping then you might be thinking of category theory and functors. Dmcq (talk) 11:56, 6 June 2010 (UTC)

Sorry, but you haven't answered my question. I've been asking whether there is a common term for a very specific mapping, i.e. a mapping induced by a first-order formula which contains logical symbols only - except for function-symbols for substituting functions which are mapped to one another by that formula. Memorandum: this formula induces a mapping whose domain and co-domain contain functions (rather than simple regular atomic points, e.g. numbers and the like.). HOOTmag (talk) 16:13, 6 June 2010 (UTC)

Niggle: given a mapping between two classes of members

What is exactly mapped? Is it one class (the domain) that is mapped into the other class (the co-domain), or is it the members of the domain that are mapped into members in the co-domain (as I've assumed in my previous thread)?? HOOTmag (talk) 11:21, 6 June 2010 (UTC)

Can refer to both and you might have a mapping into or onto or just a mapped to. Precision of language doesn't matter much when you've got the symbols. Hand waving and pointing at the board are other good ways of getting a meaning across :) Dmcq (talk) 12:02, 6 June 2010 (UTC)

I'm looking for the precise expression, and that's why I called that "niggle..." HOOTmag (talk) 16:15, 6 June 2010 (UTC)

Usually we would say "f is a mapping from D to R" where D (the domain) and R (the range) are sets; but we could informally say "f maps x to x²" referring to elements of the domain and range. I.e. $f:\mathbb {R} \to \mathbb {R}$ is the squaring function $f:x\mapsto x^{2}$ (note the differing arrow symbols for "to" and "maps to"). I agree with Dmcq that you might like to study some category theory, which examines this sort of question rather closely. 75.57.243.88 (talk) 19:59, 6 June 2010 (UTC)

Is Newton's law rigth?

1-Is F*dt=m*dv rigth? If yes,

2-Is F*r*dt=m*r*dv energy conservation equation rigth? If yes,

3-Is 1/2*m*V^2+m*g*r+1/2*I*w^2=Ct total energy equation rigth? If yes,

4-Is I*w^2=constant as an innate energy? That is I*w0^2=I*wn^2. If yes,

5-Is 1/2*m*V1^2+m*g1*r1= 1/2*m*V2^2+m*g2*r2? (at position #1 and #2). If yes,

6-Is V^2=Vr^2+Vp^2 ? (Vorbital^2=Vradial^2+Vperpandicular^2) (Vectors).If yes,

7-Is Vr1^2+2*g1*r1=Vr2^2+2*g2*r2 rigth? (Vp does not change the equality).If yes,

8-Is Vp1=Vp2=Vp3=....=Vpn=Constant rigth? If yes,

9-Why Wiki says r*Vp=Constant,and deducts Kepler's area law?

10- If (1/2*m*Vr^2+m*g*r+1/2*I*w^2=m*r*dVr) the energy conservation equation rigth ,then

11-Is 1/2*m*(dr/dt)^2+K/dt^2=m*r*d(dr/dt)/dt where (K/dt^2=m*gr*r+1/2*I*w^2)rigth? If yes,

12-Is r'^2+2*K/m/dt^2=2*r*r" the differential equation rigth? If yes,

13-Is r=-a*t^2+a*t*tmax+K where K=-a*tmax^2/4=Constant and this solution is rigth? If yes

14-How to comment r=-a*t*(t-tmax) graph on polar plane coordinates?

15-Does the last equation indicate the orbital motion of the planets? (3 dimension). TASDELEN (talk) 19:40, 6 June 2010 (UTC)

3 is wrong. By $mgr$ you probably meant the gravitational potential energy, but this is only true for constant acceleration due to gravity, and not for inverse square law. -- Meni Rosenfeld (talk) 19:48, 6 June 2010 (UTC)

Always possible to find a matrix that transform a matrix into reduced row echelon form?

Dear all,

I want to find an m-times-m matrix, Q, such that QB=E, where B is an m-times-n matrix and E is the reduced row echelon form of B. Is this always possible?

In my case Q is invertible and m>n. Does this help me?

Thank you in advance, Marc K (talk) 19:53, 6 June 2010 (UTC)