Mathematics desk
< January 14	<< Dec \| January \| Feb >>	January 16 >

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.

January 15

Coefficients of polynomial

p(x) is a polynomial

p_k(x) = product of (x - product(i)) for i in the k-th degree cartesian product of the roots of p

For example, if p(x) = (x - 1) * (x - 2), then p_3(x) = (x-1*1*1)*(x-1*1*2)*(x-1*2*1)*(x-1*2*2)*(x-2*1*1)*(x-2*1*2)*(x-2*2*1)*(x-2*2*2) = 4096 - 13824*x + 19328*x^2 - 14688*x^3 + 6648*x^4 - 1836*x^5 + 302*x^6 - 27*x^7 + x^8.

My question is, is there a way to calculate the coefficients of p_k without knowing the roots of p exactly (i.e., when p has a large degree), and when using approximations doesn't give enough precision? Will p_k always have integer coefficients? 70.190.182.236 (talk) 04:06, 15 January 2015 (UTC)[reply]

The theory of symmetric polynomials predicts that the coefficients of p_k will be polynomials in the coefficients in p. Also, p_k will factor based on grouping the Cartesian product according to the number of duplicate entries. For example, if p = x² - sx + t then p₂ = x⁴ - s²x³ + 2t(s²-t)x² - s²t²x + t⁴ = (x-t)²(x²+(2t-s²)x +t²). I doubt there is anything like a closed form expression that works for all degrees though. One way to approach it might be to make a matrix A with characteristic polynomial p, then p_k is the characteristic polynomial of A ⊗ A ⊗ ... ⊗ A, the tensor product of A with itself k times. --RDBury (talk) 05:45, 15 January 2015 (UTC)[reply]

what does 'one-way functions may not exist' mean in practice? There is no bounds at all?

Hi guys,

I'm reading the http://en.wikipedia.org/wiki/One-way_function article.

References seem to be clear that mathematically there is no proof that one-way functions (hashes) actually exist. Does this mean that there is absolutely no bounds on computational complexity that can be proved at all? For example, it could be that O(n) where n is exactly seven operations, for any hash? --- but that's clearly insane. We can know 7 operations aren't enough to produce an arbitrary hash value because we can just brute-force all 7-operation "algorithms" and prove that 7 operations won't get you a plaintext that hashes to x for any x in the space.

so there has to be some bounds, right? (obviously brute-forcing is a formal proof but an expensive one, so we can formally prove that 7 operations can't reverse sha-256)

But if there is some bounds, then what is the sense that "one-way functions don't exist." ... That we have formally proved minimum bounds (such as 7), they're just not high enough?

or what is the key insight I'm missing. thanks. 212.96.61.236 (talk) 05:20, 15 January 2015 (UTC)[reply]

Two things. One, not all (supposed) one-way functions of interest are hash functions: the one-way permutations are what you need for public-key cryptography. Two, it's not enough for inverting the function to take more than a constant amount of time: the definition says that all polynomial-time algorithms must have a vanishing chance of success. --Tardis (talk) 14:54, 15 January 2015 (UTC)[reply]

Why would that be a definition? Proving that it can't be done in under exactly 10^100 operations - which is constant-time, it's O(1) - would be an absolutely unbreakable hash. So why would anyone pick a definition like you are saying is the one that defines secure hashes? 212.96.61.236 (talk) 20:53, 15 January 2015 (UTC)[reply]

Big O notation only makes sense for algorithms that work on inputs of unbounded (or at least widely variable) size. You (the algorithm designer) don't get to choose a value of n (like 7). When talking about reversing hash functions that work with a fixed number of bits, cryptographers seem to just count steps.

You could rule out all 7-step algorithms, or maybe even all 20- or 30-step algorithms, by exhaustive enumeration, but there's no point since even computing hashes in the forward direction takes thousands of steps. SHA-256 would be utterly broken as a one-way function if you could reverse it in a billion steps, and you can't enumerate all billion-step algorithms.

I don't think anyone has proven a lower bound for this by anything other than brute force. No one really knows how to prove circuit lower bounds, and while this is not quite the same because it doesn't use big-O notation, it seems similar enough. -- BenRG (talk) 17:38, 15 January 2015 (UTC)[reply]

I know how big-O notation works, I was just being rhetorical. Why is Big(O) notation the definition used for whether a hash is secure? 212.96.61.236 (talk) 20:53, 15 January 2015 (UTC)[reply]

I don't think it is. Attacks on hashes and block ciphers always seem to quote bare step counts. See SHA-1#Attacks, for example. Big-O notation is used for the one-way functions used in public key cryptography. It is odd that the one-way function article only defines the concept in complexity-theory terms but then gives hash functions as an example. Probably the article should define the term more broadly. -- BenRG (talk) 01:12, 17 January 2015 (UTC)[reply]

Calculate p-values of PCR-estimator

Hello :-)

I followed the instructions of Principal_component_regression#Details_of_the_method (which was very exciting). I did this with statistic software R. I got final PCR-estimates, e.g.

[1,] 27.005477 [2,] 28.531195 [3,] 4.031036 [4,] 29.464202 [5,] 18.974255 [6,] 47.658639 [7,] 24.125975 [8,] 30.831690 [9,] 32.111585 [10,] 21.811584 [11,] 34.054133 [12,] 28.901388 [13,] 37.990794 [14,] 9.021954 [15,] -66.069150 [16,] 74.483241 [17,] -3.654576 [18,] -6.004836 [19,] 11.401041

I can calculate the R^2 (and adj.) and the F-statistic. But is it possible to calculate SE and p-values to check the significance? What else can I do to check whether and to what extent my PCR-Model is better than the OLS-version (original data was strongly multicollinear). I checked Principal_component_regression#Two_basic_properties and for k=p=19 I got same reg-coefficients with OLS and PCR. I also can calculate MSE-values, as in Principal_component_regression#Efficiency it says MSE of OLS should be bigger (e.g. worser) than PCR. For k=p=19 it is the same, for less components PCR-MSE gots smaller. But what else can I see from my results? Would be very thankful for any idea :-) Thanks a lot! --WissensDürster (talk) 11:49, 15 January 2015 (UTC)[reply]

Logic

The proposition "(B if C) and (C if B)", is tautologically equivalent to "B iff C", in which B is not mentioned twice.

My question is about whether, the following proposition is - tautologically equiavalent to any proposition - in which B is not mentioned twice (by using as many connectives as we wish and no matter what connectives are used, provided that all connectives are binary or unary):

"(B if C), and (C if (B and A))".

77.126.32.139 (talk) 23:10, 15 January 2015 (UTC)[reply]

I assume that you mean a restriction that does not permit ternary and connectives, since it would be trivial to define a ternary connective that needs only one mention of B to achieve this as one of its arguments. Assuming only binary connectives, my instinct (looking at a Karnaugh map of the logic) is that the answer will be 'yes'. However, this looks somewhat like a homework problem, so I am hesitant to give the solution. (This is also a great excuse for not rigorously checking my solution!) —Quondum 00:26, 16 January 2015 (UTC)[reply]

Is "(B if C)" meant to be read as "If B then C" or "If C then B"?--80.109.80.31 (talk) 04:56, 16 January 2015 (UTC)[reply]

I see no other way to interpret this than "If C then B", i.e. (B ← C), or (C implies B). —Quondum 05:02, 16 January 2015 (UTC)[reply]

Yes, "B if C" means "B ← C".

Yes, I mean binary (or unary). I have just added this important restriction to my original formulation, Thank you !

No, it's absolutely not a homework question, it's a real question !

No, I don't share with you the same intuition (I have no prior intuition though). I suspect Karnaugh Map may not be helpful here, since it permits the OR / AND / NOT only, so that even my first example - "(B if C) and (C if B)" - can't be abbreviated by that map.

77.126.32.139 (talk) 06:10, 16 January 2015 (UTC)[reply]

Homework questions are real questions. What can you conclude if A holds? That is A → what? YohanN7 (talk) 13:07, 16 January 2015 (UTC)[reply]

A note on the use of a Karnaugh map: the connective 'iff' (↔/=) and XOR can be inferred from a checkerboard pattern (which I used to get something that looks the same as CiaPan's second answer below). —Quondum 17:09, 16 January 2015 (UTC)[reply]

If I did my calculations correctly, "(B if C), and (C if (B and A))" is equivalent to "B or (not A and not C)". --CiaPan (talk) 13:10, 16 January 2015 (UTC)[reply]

Well, I did it wrong. --CiaPan (talk) 13:44, 16 January 2015 (UTC)[reply]

But this seems a good answer: "(B equals C) or (not A and not C)". --CiaPan (talk) 15:02, 16 January 2015 (UTC)[reply]

Correct ! thank you so much ! Btw, your answer can be abbreviated further: "(B iff C) if (A or C)". 77.126.32.139 (talk) 14:07, 18 January 2015 (UTC)[reply]

If A then (C if B) from (C if (B and A)). Since (B if C) always, A → (B ↔ C). This is the same as ¬(B ↔ C) → ¬A (but not ¬(B ↔ C) → (¬A ∧ ¬C)). YohanN7 (talk) 15:20, 16 January 2015 (UTC)[reply]

A → (B ↔ C), is a wrong answer. Check when only C is true. 77.126.32.139 (talk) 14:07, 18 January 2015 (UTC)[reply]

Can't happen, because C → B. --jpgordon^{::==( o )} 16:42, 18 January 2015 (UTC)[reply]

It can happen, that only C is true, in which case: my original proposition (about which I've asked) would be false (because C → B as you have pointed out), whereas YohanN7's proposition - would be true - and consequently couldn't be tautologically equivalent to my original proposition. 77.126.32.139 (talk) 18:30, 18 January 2015 (UTC)[reply]

Right, while A → (B ↔ C) is a logical consequence, it is not the only one and hence not a logical equivalence. You have [A → (B ↔ C)] ∧ [C → (B ↔ C)] which is false for only C true. YohanN7 (talk) 01:55, 19 January 2015 (UTC)[reply]

Please note that your new proposition, [A → (B ↔ C)] ∧ [C → (B ↔ C)], mentions B twice, so it can't be the proposition I'd been looking for. Yet, you could reduce it to the shortened form [A V C] → (B ↔ C)], in which B is not mentioned twice; However, I have already referred to this shortened form - in my response to CiaPan (see above). 77.126.32.139 (talk). 08:14, 19 January 2015 (UTC)[reply]

Resolved