Wikipedia:Reference desk/Archives/Mathematics/2016 March 18

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

March 18

Quadratic Equation

Hi, is the following problem NP-hard or co-NP hard?

Problem: Given a quadratic polynomial, P, does it hold that $\forall x\in \{0,1\}^{n}\ P(x)=0$? Thanks in advance! :) 213.8.204.64 (talk) 07:39, 18 March 2016 (UTC)

Moved from RD/C Tevildo (talk) 08:40, 18 March 2016 (UTC)

What do you mean by applying a polynomial to a string? — Preceding unsigned comment added by 2406:E006:1B18:1:D186:6CB1:9890:E844 (talk) 12:12, 18 March 2016 (UTC)

I believe the OP meant this is a multivariate polynomial, and the entries of the n-tuple are its different variables. -- Meni Rosenfeld (talk) 13:22, 18 March 2016 (UTC)

In that case take x = (x₁, ... x_n) a vector of dimension n and P a quadratic function of n variables. I'm pretty sure that P is zero on {0, 1}ⁿ iff P(x₁, ... x_n) is a linear combination of x_i²-x_i. If so, then applying this criterion answers the question in polynomial time. --RDBury (talk) 13:49, 18 March 2016 (UTC)

Meni - this is what I meant.

RDBury, It's an interesting conjecture. However, I don't succeed to prove (or disprove) it..

Further, does its generalization hold for cubic polynomials (and similarly for polynomials of any degree) - cubic polynomial P is zero on $\{0,1\}^{n}$ iff it's a linear combination of $(x_{i}^{2}-x_{i})x_{j}$ (maybe i=j)? 213.8.204.45 (talk) 06:12, 19 March 2016 (UTC)

That would be $x_{i}^{2}-x_{i}$ and $x_{i}^{3}-x_{i}$, but with cubics it sounds awfully like the 3SAT problem to me. Dmcq (talk) 18:24, 19 March 2016 (UTC)

There's probably easier ways to prove it using tools from algebraic geometry, but here's a somewhat naive attempt. I want to show, given P is a quadratic polynomial, P(x₁, ... x_n) is 0 on {0, 1}ⁿ iff P is a linear combination of x_i²-x_i. The ⇐ direction is clear so it remains to show the ⇒ direction. Let P be quadratic polynomial which is is 0 on {0, 1}ⁿ. If the coefficient of x_i² is not zero, say c_i, then replace P with P-c_i(x_i²-x_i). This changes neither the values on {0, 1}ⁿ nor whether P is a l.c of x_i²-x_i. So wlog the only quadratic terms in P are of the form x_ix_j. P can be written a+bx_i+cx_j+dx_ix_j where a, b, c, d are functions of the remaining variables, a quadratic, b, c linear and d is the coefficient of x_ix_j in P. Assign values the remaining variables to so a, b, c become constants and P becomes a function of x_i and x_j. Then P(0,0)=a=0, P(1, 0)=a+b=0, P(0,1)=a+c=0 and P(1,1)=a+b+c+d=0. These imply a=b=c=d=0. In particular, d, the coefficient of x_ix_j in P, is 0, and applying this to all i and j this shows that P is in fact linear. {0, 1}ⁿ contains n+1 affinely independent points so P=0 on these points now implies P is 0 and the result is proved.

If you don't restrict yourself the quadratic polynomials then the P is 0 on {0, 1}ⁿ iff P is in the ideal of R[x₁, ... x_n] generated by the x_i²-x_i. The proof is as above except now you need to show that if P has only terms which are linear in each variable and P is 0 on {0, 1}ⁿ then P is 0. Let V be vector space of polynomials with only terms which are linear in each variable, so dim(V)=2ⁿ. Let L be the linear map V→R²ⁿ defined by evaluating at each point in {0, 1}ⁿ. In fact, L is onto, since if I multiply factors of the form (x_i) or (1-x_i) I can get a P∈V which maps to a standard basis vector, and the 2ⁿ possible products map to the 2ⁿ basis vectors. By comparing dimensions, the kernel must be 0, which is what was needed to be shown. Note that this version easily implies the statement about quadratic polynomials.

@Dmcq Note x_i³-x_i=(x_i²-x_i)(x_i+1). Not sure what happens if you try to apply this to 3sat but I assume that in the transition from a logical expression to algebraic you get additional terms which make the number of terms exponential in terms of n. --RDBury (talk) 19:46, 19 March 2016 (UTC)

Thank you very much! 2001:BF8:200:FF99:6D72:8A4C:ED75:BB92 (talk) —Preceding undated comment added 10:57, 21 March 2016 (UTC)

Dining Couples Combinatorial Problem

I finally have a chance to use combinatorial skills on a real world problem, but the solution isn't coming to me... I have 40 couples. They want to go to dinner every month in groups of 4 couples. To be clear, each couple consists of 2 people that will always be together, treated as one unit. The dinner will have 8 people, which is 4 couples, which is 4 atomic units. They don't want four couples to repeat a dinner by sharing it with the same other three couples. They want every dinner night to consist of 10 dinners at which none of the four couples have already had dinner. Obviously, a single couple cannot show up twice to the same dinner. In other words, a dinner cannot consist of couples A, A, B, and C. Further, a couple cannot show up to two different dinners on the same night. You can't have dinner A, B, C, D, and dinner A, E, F, G on the same night. How many nights can I ensure that every dinner is unique? I've tried to do it by hand and I can only do three nights, then I lose track of everything and I can't figure out a fourth night. 209.149.113.14 (talk) 17:59, 18 March 2016 (UTC)

To clarify: you mean that exactly 40 couples go to exactly 10 events of four couples each, exactly once per month? SemanticMantis (talk) 18:05, 18 March 2016 (UTC)

Correct. There are 40 couples (atomic units). They want to go to dinner on different nights. Each of those nights, they will be in groups of 4 couples (10 dinners total, each with 4 couples). They never want to have a dinner with the same four couples at it. I initially thought it was easy because we do that for sports leagues all the time. We don't do it with 4 teams per game. 209.149.113.14 (talk) 18:17, 18 March 2016 (UTC)

We need to define the terms more clearly, avoiding the term "dinner", since that could mean either a night or a table:

N = Night, an event with 10 tables, each consisting of 4 couples. How many nights are desired ? As many as possible ? N = 12.

T = Table, a group of 4 couples that dine together. Each table should never have any 2 couples who have been at a common table before, on this night or any other, right ? Each table should never have the exact same 4 couples who have been at a table before, but 2 of the same couples or 3 of the same is OK.

C = Couple, two people who always dine together. There are 40 couples. StuRat (talk) 18:26, 18 March 2016 (UTC)

The tables (T) should be unique. If couples {A, B, C, D} have dined before, you can later have couples {A, B, C, E}. That is a different dinner. They want to fill up a year's worth of monthly dinner nights. That would be 12 nights. 209.149.113.14 (talk) 18:36, 18 March 2016 (UTC)

Good, info added. I will take a look at the problem now. StuRat (talk) 19:06, 18 March 2016 (UTC)

It seems to me that if the rule was implemented that once two couples dined they would never dine again, it will really trim down the possibilities and, with a cursory look, I can only get 8 nights before I am forced to do a repeat. 209.149.113.14 (talk) 19:08, 18 March 2016 (UTC)

Yes, I don't believe N=12 would be possible, under that rule. StuRat (talk) 20:06, 18 March 2016 (UTC)

I start with the observation that:

 1×4 couples per table =  4, which is divisible into 40 couples.
 2×4 couples per table =  8, which is divisible into 40 couples.
 5×4 couples per table = 20, which is divisible into 40 couples.
10×4 couples per table = 40, which is exactly 40 couples.

So, I will use offsets of 1, 2 and 5, with various starting points, to meet the goal of N=12.

Thus, I would start with every couple in order (offset = 1 between each couple), like this, with initial starting points of 1, 2, 3, and 4:

   N = 1         N = 2         N = 3         N = 4
===========   ===========   ===========   ===========
01 02 03 04   02 03 04 05   03 04 05 06   04 05 06 07
05 06 07 08   06 07 08 09   07 08 09 10   08 09 10 11
09 10 11 12   10 11 12 13   11 12 13 14   12 13 14 15
13 14 15 16   14 15 16 17   15 16 17 18   16 17 18 19
17 18 19 20   18 19 20 21   19 20 21 22   20 21 22 23
21 22 23 24   22 23 24 25   23 24 25 26   24 25 26 27
25 26 27 28   26 27 28 29   27 28 29 30   28 29 30 31
29 30 31 32   30 31 32 33   31 32 33 34   32 33 34 35
33 34 35 36   34 35 36 37   35 36 37 38   36 37 38 39
37 38 39 40   38 39 40 01   39 40 01 02   40 01 02 03

Then do every other couple (offset = 2 between each couple), like this, with starting points of 1, 3, 5, and 7:

   N = 5         N = 6         N = 7         N = 8
===========   ===========   ===========   ===========
01 03 05 07   03 05 07 09   05 07 09 11   07 09 11 13
02 04 06 08   04 06 08 10   06 08 10 12   08 10 12 14
09 11 13 15   11 13 15 17   13 15 17 19   15 17 19 21
10 12 14 16   12 14 16 18   14 16 18 20   16 18 20 22
17 19 21 23   19 21 23 25   21 23 25 27   23 25 27 29
18 20 22 24   20 22 24 26   22 24 26 28   24 26 28 30
25 27 29 31   27 29 31 33   29 31 33 35   31 33 35 37
26 28 30 32   28 30 32 34   30 32 34 36   32 34 36 38
33 35 37 39   35 37 39 01   37 39 01 03   39 01 03 05
34 36 38 40   36 38 40 02   38 40 02 04   40 02 04 06

Then do every 5th couple (offset = 5 between each couple), like this, with starting points of 1, 6, 11, and 16:

   N = 9         N = 10        N = 11        N = 12
===========   ===========   ===========   ===========
01 06 11 16   06 11 16 21   11 16 21 26   16 21 26 31 
02 07 12 17   07 12 17 22   12 17 22 27   17 22 27 32
03 08 13 18   08 13 18 23   13 18 23 28   18 23 28 33 
04 09 14 19   09 14 19 24   14 19 24 29   19 24 29 34
05 10 15 20   10 15 20 25   15 20 25 30   20 25 30 35
21 26 31 36   26 31 36 01   31 36 01 06   36 01 06 11
22 27 32 37   27 32 37 02   32 37 02 07   37 02 07 12
23 28 33 38   28 33 38 03   33 38 03 08   38 03 08 13
24 29 34 39   29 34 39 04   34 39 04 09   39 04 09 14
25 30 35 40   30 35 40 05   35 40 05 10   40 05 10 15

I believe a 13th N is possible, using every 10th couple at a table, but different starting points don't change the combinations there, since 4×10 is exactly 40 (so if we start at 11, for example, we get 11,21,31,01, which is exactly the same as 01,11,21,31):

   N = 13
===========
01 11 21 31
02 12 22 32
03 13 23 33
04 14 24 34
05 15 25 35
06 16 26 36
07 17 27 37
08 18 28 38
09 19 29 39
10 20 30 40

Did I make any mistakes ? StuRat (talk) 20:01, 18 March 2016 (UTC)

A keyword: this question belongs to the study of combinatorial designs. --JBL (talk) 20:22, 18 March 2016 (UTC)

I believe Baranyai's theorem applies here with m=4, k=40. I have no idea how the theorem is proved though. --RDBury (talk) 06:24, 19 March 2016 (UTC)

If anyone is interested in going beyond $N=12$, a quasi-random greedy search that I tried routinely reaches 4600 nights (still far from the theoretical 9139). --Tardis (talk) 07:10, 22 March 2016 (UTC)

Hyperbolic tangent converges to 1

Why does $\lim _{x\to \infty }\tanh(x)$ equal 1? 63.251.215.25 (talk) 20:36, 18 March 2016 (UTC)

What have you tried? --JBL (talk) 21:03, 18 March 2016 (UTC)

• Consider the definition: $\tanh x=({e^{x}-e^{-x}})/({e^{x}+e^{-x}})$. What can you say about the asymptotic behavior of any part of that expression? —Tamfang (talk) 21:02, 19 March 2016 (UTC)