Wikipedia:Reference desk/Archives/Mathematics/2017 February 9

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.

February 9

Question 11

How do I go about proving (11) here? The problem says:

If a is a constant and A an n×n square matrix, then

|aA| = aⁿ |A|

I wrote the general matrix out like so:

$\mathbf {A} ={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\end{bmatrix}}$

However, I wasn't sure how to proceed from here. I already wrote out the 2×2 and 3×3 cases, I just wasn't sure how to prove the general case shown above. 147.126.10.21 (talk) 04:00, 8 February 2017 (UTC)

There are several approaches, depending on what properties of the determinant you can assume. Here are three possibilities:

1. Start with the Leibniz formula for determinants and note that the determinant of a nxn matrix is a polynomial in which each term is the product of n matrix elements.
2. Start from the property that the determinant of a nxn matrix is the product of its n eigenvalues. How are the eigenvalues of aA related to the eigenvalues of A ?
3. Start from the Laplace expansion which expresses the determinant of a nxn matrix as the weighted sum of the determinants of certain n-1 x n-1 sub-matrices. This allows a proof by induction.

Gandalf61 (talk) 09:31, 8 February 2017 (UTC)

Also, the questioner should be aware that his explicit statement of the matrix A shows it to be m×n, but the determinant is only defined if m=n. Loraof (talk) 18:28, 8 February 2017 (UTC)

Is the last line a typo?

[1] Isn't this a scalar function even when applied to a vector field? Thank you. 69.22.242.15 (talk) 04:19, 9 February 2017 (UTC)

No. $\nabla ^{2}P$, $\nabla ^{2}Q$, and $\nabla ^{2}R$ are individually scalar functions of $(x,y,z)$. $\nabla ^{2}\,{\mathbf {F} }=\nabla ^{2}P\,{\mathbf {i} }+\nabla ^{2}Q\,{\mathbf {j} }+\nabla ^{2}R\,{\mathbf {k} }$ is a vector-valued function. --100.34.204.4 (talk) 05:54, 9 February 2017 (UTC)

In that case the result of div can be either scalar or vector, so we can't say that it produces a scalar or vector field without specifying its input? Also, div <P,Q,R> = Px +Qy + Rz so how is that a vector? 69.22.242.15 (talk) 13:01, 9 February 2017 (UTC)

Divergence is defined on a vector field. I don't think it's meaningful to talk about the divergence of a scalar field.

As an operator, $\nabla ={\frac {\partial }{\partial x}}{\mathbf {i} }+{\frac {\partial }{\partial y}}{\mathbf {j} }+{\frac {\partial }{\partial z}}{\mathbf {k} }$, so $\nabla ^{2}=({\frac {\partial ^{2}}{\partial x^{2}}},{\frac {\partial ^{2}}{\partial y^{2}}},{\frac {\partial ^{2}}{\partial z^{2}}})$, which is a vector-valued function.

Applying the latter to ${\mathbf {F} }$, where ${\mathbf {F} }=P\,{\mathbf {i} }+Q\,{\mathbf {j} }+R\,{\mathbf {k} }$ and $P$, $Q$, $R$ are scalar functions of $(x,y,z)$, we have $\nabla ^{2}{\mathbf {F} }={\frac {\partial ^{2}P}{\partial x^{2}}}{\mathbf {i} }+{\frac {\partial ^{2}Q}{\partial y^{2}}}{\mathbf {j} }+{\frac {\partial ^{2}R}{\partial z^{2}}}{\mathbf {k} }$, which is quite obviously vector-valued.

$\operatorname {div} {\mathbf {F} }$ is indeed a scalar field, but $\operatorname {div} {\mathbf {F} }$ is not the same as $\nabla ^{2}\,{\mathbf {F} }$. --100.34.204.4 (talk) 22:44, 9 February 2017 (UTC)

See Divergence (∇ · F) for the operator that produces a scalar field. Dbfirs 23:30, 9 February 2017 (UTC)

This is all simplified, though I am afraid simplified might not be your opinion of it, when dealing with differential manifolds in Stokes' theorem which covers all these variations in a much cleaner fashion. In it instead of producing a result of dimension d in the same space the equivalent operation may produce a result of dimension N-d in a dual of the space. Dmcq (talk) 13:49, 10 February 2017 (UTC)

n⁴ divides Central binomial coefficient

What is the smallest non-trivial solution (i.e., n > 1) to n⁴ dividing Binomial (2n, n) ? All I know is that n > 10⁷. This is related to these three integer sequences. — 86.125.207.71 (talk) 08:20, 9 February 2017 (UTC)

I suspect there is none. Someone may have a more rigorous proof, but, first you need only consider primes, as if n composite is a solution then its prime factors are. And for any prime p I can’t see how you can have four (or more) of them on top of the fraction ${\frac {(2n)!}{(n!)^{2}}}.$. You can write out the factors on the top and bottom and in each case it’s just lists of numbers. (1 × 2 × 3 ... 2n) / ((1 × 2 × 3 ... n) × (1 × 2 × 3 ... n)). Any prime appears about as often in the numerator and denominator.--JohnBlackburne^words_deeds 09:00, 9 February 2017 (UTC)

I'm not convinced. If valid, why would that argument not work for n³ | Binomial (2n, n)? There seems to be an infinite number of solutions in that case. (See the first linked oeis sequence.) The programs listed to generate the oeis sequences just use a brute force search, but you could probably find an upper bound on the highest prime factor of n that might narrow the search a bit. --RDBury (talk) 09:17, 9 February 2017 (UTC)

PS. If you look at the graphs of the other sequences they seem fairly linear. So heuristically you could argue that the probability of an integer being in the sequence is constant. For n | Binomial (2n, n) the probability seems to be about 1/9, For n² | Binomial (2n, n) about 1/600, and for n³ | Binomial (2n, n) about 1/200000. Assuming that n⁴ | Binomial (2n, n) keeps to the same pattern then its probability would be very low, say 1 in a billion, but still >0. So you wouldn't expect searching up would 10⁷ produce any solutions, but searching up to 10¹⁰ might. --RDBury (talk) 09:51, 9 February 2017 (UTC)

As can be quite easily glimpsed from the linked articles, the first non-trivial solutions to Binomial(2n,n) being divisible by n^k (for k = 1, 2, 3) are 2, 924, 154836. Therefore, I deem it rather reasonable to expect a first solution for k = 4 somewhere in between n = 10⁷ and n = 10⁸. — 86.125.207.71 (talk) 10:56, 9 February 2017 (UTC)

• if n composite is a solution then its prime factors are - hmm, no. Actually, you have written the reason: it is fairly simple to see that no prime number verifies the OP's property: for prime p>2, p never divides ${2p \choose p}$, much less to the power 4; but it is not the case for composite numbers (e.g. 6^2=36 divides ${12 \choose 6}=252$ because there are enough 2s and 3s in the list). Tigraan^{Click here to contact me} 12:10, 9 February 2017 (UTC)

Make that "for prime $p>2$". $p=2$ is special because $2p$ happens to be $p^{2}$. -- Meni Rosenfeld (talk) 12:36, 9 February 2017 (UTC)

• Here's a thought. Using the p-adic valuation theory, in particular Legendre's formula, $v_{p}\left({2N \choose N}\right)=v_{p}((2N)!)-2v_{p}(N!)=\sum _{i=1}^{\infty }\left\lfloor {\frac {2N}{p^{i}}}\right\rfloor -2\left\lfloor {\frac {N}{p^{i}}}\right\rfloor \leq \log _{p}(N)+1$ (the inequality comes from counting the number of nonzero terms in the sum). On the other hand, $v_{p}\left(N^{k}\right)=kv_{p}(N)$.

Now, this does not give possible solutions, because $\sum \left\lfloor {\frac {2N}{p^{i}}}\right\rfloor -2\left\lfloor {\frac {N}{p^{i}}}\right\rfloor$ may well be 0 even for large N. However, it proves that some numbers are not solutions: for instance, p^m (with p prime) will never work, because the p-adic order of the binomial coefficient will be at most m+1 whereas that of n^k will be km (>m+1 for k>1, m>1). (The OP's case is k=4)

Moreover, if you want to run a computer test, it is certainly waaay faster to test it this way than actually computing the binomial coefficients. Decompose N in prime factors, compute the p-adic valuation of the binomial coefficient for all prime factors (from simple division / rounding operations of the formula above), compare. I have the feeling that the best candidates are numbers of the form 2*3*5*7*... but I cannot prove it. Tigraan^{Click here to contact me} 12:41, 9 February 2017 (UTC)

I agree that this approach would find solutions much faster than a brute force search. What I'm worried about is the "Decompose N in prime factors" step if you were trying to find all solutions. Perhaps it would be instructive to look at the factorizations for the k=3 case to get a better idea of the "prime profile" for the ideal candidate. The first five entries are 2²⋅3²⋅11⋅17⋅23, 2³⋅3²⋅5⋅7⋅17⋅23, 2³⋅3⋅11⋅13⋅17⋅19, 7⋅11⋅17⋅23⋅37, 2²⋅3⋅5⋅7⋅11⋅17⋅19. It certainly appears that good candidates smooth in some sense, but note that some entries are odd and others are not divisible by 3. It also appears the the number of distinct primes is also important since there are none on the list with less than 5. Perhaps the best way would be to go through integers <10¹⁰ having at least 6 different prime factors. Or just to get things moving, test all integers of the form 2⋅3⋅5⋅7⋅11⋅13⋅N. --RDBury (talk) 00:18, 10 February 2017 (UTC)

What do you mean by What I'm worried about is the "Decompose N in prime factors" step if you were trying to find all solutions. ? Are you saying that the algorithm might not detect certain viable solutions which do not fit into its pattern, or that you're worried such an approach might (still) be too time consuming ? — 79.113.196.30 (talk) 05:35, 12 February 2017 (UTC)

The smallest non-trivial solution for n⁴ is 227736432 = 2⁴ × 3² × 7 × 11 × 19 × 23 × 47. It is the 2480th non-trivial solution for n³. PrimeHunter (talk) 01:16, 10 February 2017 (UTC)

Is this from a brute force search or did you use some of the divisibility ideas discussed? --RDBury (talk) 02:04, 10 February 2017 (UTC)

I used some of the discussed ideas in a 10-line PARI/GP script with some shortcuts to avoid repeating a lot of work for each number. I could have made a far faster C program with a better algorithm but this was sufficient and much easier to code. According to my calculations (not formally proved) the largest prime factor in a solution x for n^k must be below the kth root of 2x, and maybe also the (k+1)th root. The 4th root of 2 × 227736432 is 146, and the fifth is 54. To be safe I tested all numbers with no prime factor above prime(100) = 541. PrimeHunter (talk) 03:11, 10 February 2017 (UTC)

The first four n⁴ solutions if you want enough for an OEIS sequence: 227736432 (2⁴×3²×7×11×19×23×47), 338956200 (2³×3²×5²×11×17×19×53), 386160984 (2³×3²×11×17×23×29×43), 482213160 (2³×3²×5×11×13×17×19×29). Some n³ solutions skip many of the smallest primes. The first with no prime factor below 30: 422959567 = 31×41×43×71×109. PrimeHunter (talk) 18:41, 10 February 2017 (UTC)

Nice. It appears in this case too that the density is relatively constant at about 1 in 100000000 or about an order of magnitude more that my initial guess. There are several conjectures you could make based on this, for example: If N_k(M) is the number of solutions of n^k | Binomial (2n, n) for n≤M, then there is c_k>0 so that N_k(M)>c_kM. I don't know if this is provable with currently available methods, but I do know it's way outside my area of expertise. --RDBury (talk) 09:49, 11 February 2017 (UTC)

On notation: 2⁴×3²×7×11×19×23×47 =2⁴3²7¹11¹19¹23¹47¹. Bo Jacoby (talk) 04:44, 12 February 2017 (UTC).

Uncomputable numbers and randomized algorithms

I think(!) that I dimly understand all the component terms of the headline. My question: is it possible for a number to be uncomputable (no algorithm can find the nth digit of its decimal, or otherwise, expansion) but for there to be a randomized algorithm that converges to said number almost surely?--Leon (talk) 22:44, 9 February 2017 (UTC)

It is not difficult to derandomize random algorithms if all you care about is computability (rather than computation time): just exhaustively check all possibilities for the random choices. You may or may not consider this an answer to your question, depending on what you mean by asking for a random algorithm to converge almost surely. --JBL (talk) 03:29, 10 February 2017 (UTC)

Almost surely. Tigraan^{Click here to contact me} 09:01, 10 February 2017 (UTC)

You will notice that that page discusses almost sure convergence of events, but not of algorithms. --JBL (talk) 14:56, 10 February 2017 (UTC)

 

(ec) I think it's pretty clear what it means. Consider an ordinary program that is deterministic except that it can query an oracle, with the oracle producing an infinite sequence of zeroes and ones. The program also outputs an infinite sequence of zeroes and ones (it's not hard to design a program so it can't halt or get stuck and not print anything else out).

Then there's a well-behaved probability measure on the set of possible oracles. Take it (for example) to be the obvious one, the so-called coin-flipping measure. That induces a probability measure on the space of possible outputs of the program.

Now, for some programs, there will be a single output sequence that gets probability 1 in the induced measure. For example, the program could unconditionally ignore the oracle and print all zeroes, and then the constant-zero sequence will have probability 1.

Leon is asking whether there is some such program for which some output sequence S has probability 1, but where S is not computable (by a deterministic program without the ability to query a random oracle).

My intuition is, no, of course there is no such program. But off the top of my head I don't have a proof. You can't "exhaustively check all possibilities for the random choices" because there are continuum-many such choices. --Trovatore (talk) 09:09, 10 February 2017 (UTC)

Oh, wait. The map from oracles to outputs is continuous. So since {S} is closed, the set of oracles that map to S would have to be a closed set of measure 1, which means it's the whole space. So then every oracle maps to S, and you can just pretend the oracle always returns 0, and you will wind up getting S. Therefore S is computable. That may boil down to what JBL meant. --Trovatore (talk) 09:19, 10 February 2017 (UTC)

I wasn't thinking about it in quite this language, but they are very close. (In this language, I may have been assuming an effective bound for delta in terms of epsilon in the continuity, in which case this is a better way to put things.) --JBL (talk) 15:03, 10 February 2017 (UTC)

The explicit way of putting it without so much topology would be like this. Suppose S is the unique output that happens with probability 1, but if the oracle returns all zeroes, then the output is T. Suppose n is smallest such that the nth bit of S differs from the nth bit of T. Without loss of generality, we'll say the nth bit of S is 0 but the nth bit of T is 1.

Then, since any finite calculation can depend on only finitely many queries to the oracle, there is some number M such that, whenever the first M queries to the oracle respond with 0, the nth bit of the output is 1 (and therefore in particular the output is not S).

But that has probability 1/2^M of happening, which is not zero, which contradicts the assumption that the output is S with probability 1. --Trovatore (talk) 19:42, 10 February 2017 (UTC)

It's a standard result of computability theory that the Turing cone above any noncomputable real is measure 0.--2406:E006:288:1:C8CA:9861:8841:96B4 (talk) 23:52, 10 February 2017 (UTC)

I knew that at some point. Probably even now. Didn't make the connection, though. (Also, it's nice to have direct proofs when available.) --Trovatore (talk) 01:11, 11 February 2017 (UTC)

 

Actually, I think the proof of the Turing-cone result (or at least the proof I can think of) goes through the special case. Suppose some Turing cone is not measure 0. The cone is F_σ and therefore measurable, so for any ε>0, there's a basic open set such that the cone restricted to the basic open set has density at least 1−ε. But a basic open set in the space of oracles is determined by some finite initial sequence, and changing a finite initial sequence doesn't change what you can compute from the oracle. Therefore the measure of the cone is at least 1−ε. But ε was arbitrary, so the measure of the cone is 1.

Now apply the earlier result to see that the cone is actually the whole space, so the base of the cone is computable. --Trovatore (talk) 09:35, 11 February 2017 (UTC)

Not exactly, because you haven't dealt with nonuniformity. The special case was for a single Turing functional, while this is for all reductions. But the proof is similar.

If a positive measure of oracles computes A, then there is some e such that a positive measure computes with functional e. Now there's some basic neighborhood such that the oracles that compute A via e have density strictly greater than 1/2. Now run a majority vote algorithm: to determine A(n), search until you've seen more than half the oracles of the neighborhood agree on an answer. That's the right answer.--2406:E006:288:1:C190:5642:9C69:8C12 (talk) 16:23, 11 February 2017 (UTC)