Wikipedia:Reference desk/Archives/Mathematics/2009 December 1

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.

December 1

Exponential or Super-Exponential Growth In A Novel Sequence

Consider the following process for forming a sequence of increasing positive integers. Begin with first term 1 and append digits to the left in binary in such a way that a 1 is placed as soon as the number so formed is relatively prime to all of its predecessors. Thus the tenth term in the sequence--from which the others can be read--is 110011100110111₂=26423. It's patently obvious that this sequence is at least exponential over the long haul, but I cannot tell whether it is more than exponential. If anybody would be interested in taking a crack at answering this inquiry, I would appreciate it.Julzes (talk) 05:52, 1 December 2009 (UTC)

Just clarifying that the sequence in binary is {1, 11, 111, 10111, 110111, 100110111, 1100110111, 11100110111, ...}, where 1111 is NOT the fourth term because it has the already used factor 11, the sixth term is neither 1110111 nor 10110111 as the first is a multiple of 111 and the second has factor 11, and so on. There are several interesting questions I could ask about the sequence, but just wondering if there might only be a finite number of primes in the sequence led me to ask the one I have. As far as I have taken the sequence, the prime with 166 binary digits is only followed by another prime when the number of digits reaches 1732. It is not difficult to demonstrate that after a certain point strings of 0s in the number become multiples of 16 in length. The question asked is essentially equivalent, I believe, to asking whether the average ratio of the number of 0s to the number of 1s increases only linearly or whether it is faster than that.Julzes (talk) 07:50, 1 December 2009 (UTC)

The question is whether term a_n is O(Cⁿ) for some constant C.Julzes (talk) 13:57, 1 December 2009 (UTC)

Since it's been a while and no one else has responded, it looks like you've looked into this a lot more than anyone else has and the problem seems very difficult. The only thing I did was to look up 1,3,7,23,55 on OEIS to see if it's a known sequence, but it didn't turn up any hits. A more basic question is whether the sequence is infinite.--RDBury (talk) 18:25, 1 December 2009 (UTC)

I've concluded that the sequence is actually almost certainly finite: The most likely ending is with 7, 13 and 97 (or 241 or 673)alternating in taking away a third of the presumptive terms. It is a very long finite sequence, however.Julzes (talk) 18:23, 1 December 2009 (UTC)

That is to say that if/when 7, 13 and 97 (in no particular order) turn out to be factors of consecutive values (by attaching 1 followed by sixteen, thirty-two and forty-eight 0s), then the sequence is complete. Other possibilities may preclude this particular end, but it is far and away the most likely (I think). Incidentally, it is the Fermat primes that are responsible for the 0s coming in strings of multiples of 16 in length. I have now taken the sequence beyond where all of the primes under 100 have been used (around 6600 binary digits, under the assumption that no big prime has snuck a fast one on me). I do seem to be helping myself here more than anything, but it's quite likely beyond my skills and patience to get some solid conclusion.Julzes (talk) 00:27, 2 December 2009 (UTC)

I'll just type out the encrypted number quickly to avoid an edit conflict, and then explain in a moment.

@&!1@&!2@1#1#1#1!11&@2^3&11@1412!333!33!21111@1@23224!2!2!3!111324@11251411$22!251!4!45!21!5511!11!2!51@2!633@2211!11!23!1!12@24321#1122315311!123!21@1#7321@1!21!6111$1!14!525!221!1!5B257!15#2327^1B44!27221!161142811A#11445!3!2221$521!36!445414!2E4!1!14223114@F111@1!5242!3!3!3!1!12@51221126112!45@12#5!2!3@51!224@1112527221$3!1!1!1264!148114425!351!74!31#1#D@6@21!14125411334!32!31324!9161!121!6215E122415@2!3345!114!132221112!1231!111@13@1@31!33!6512@3!238!232142@2351!12116D!1. Julzes (talk) 05:20, 3 December 2009 (UTC)

I hereby award you this year's Annual Shannon Prize for the Most Outstanding Piece of Line Noise. Congratulations! — Emil J. 13:34, 3 December 2009 (UTC)

I'm 99% certain that what I have just typed or something close to it (typos?) is the complete number for the process I have described. It's a 16002-digit binary number; and the fact that 7, 13 and 97 are factors of 2^48-1 was critical, as predicted. The way to read the above is as follows. It is essentially a modified counting of strings of 1s and 0s, and it reads in reverse order from the number itself to reflect the process that formed it. The character '&' is a special character meaning that this is the current minimum number of 0s in a row and the last time it appears, doubling each time. The numbers represent the multiple of this minimum, and A through F are extensions as in hexadecimal. Single, isolated 1s are not counted, and the characters representing the excess in length are the shifted digits (Two 1s is '!', three is '@', etc., with '&' being an exception--the maximum is seven in a row). That's about it, in case someone wants to check my result.Julzes (talk) 05:36, 3 December 2009 (UTC)

See OEIS: A168612.

Wow! The Annual Shannon Prize and another OEIS entry. Thanks, folks.Julzes (talk) 16:02, 3 December 2009 (UTC)

I suppose I should clear up the specifics related to my use of an American keyboard. After '!' and '@', the shifted digits continue with '#', '$', '%', '^' and '&'.Julzes (talk) 03:52, 4 December 2009 (UTC)

negative exponent dividend

The square root can be written in exponent notation as x ^1/2 according to the article. What happens when the dividend is negative, i.e. x ^-1/2? Is the graph a mirror image and if so what does it look like? 71.100.8.206 (talk) 06:58, 1 December 2009 (UTC)

Note that, $x^{-{\frac {1}{2}}}={\frac {1}{x^{\frac {1}{2}}}}$. The graph of $y=x^{\frac {1}{2}}$ is included in the image. The graph corresponding to the negative exponent will behave as follows: as x increases, the graph will approach the x-axis from above, and as x approaches zero, the graph will move indefinitely along the y-axis, upwards. Alternatively, you can visualize the graph as an "arc" from the top of the square depicted to the side on the right. --PST 07:55, 1 December 2009 (UTC)

ec. There is not a big similarity between the graph of the function x^1/2 and its multiplicative inverse or reciprocal x^-1/2=1/(x^1/2). In general, there is a mirror simmetry (wrto the diagonal), between the graph of a (bijective) function and the graph of its inverse function. Actually your x^-1/2 is the inverse function of 1/x², so you should compare the graphs of these two.

To get a better understanding, note that for any real value of α you have a function f_α:[0,∞)→[0,∞) defined as f_α(x):=x^α. Draw the graphs of these functions for various values of α and compare them. Then you should try to understand:

1. what is the multiplicative inverse of f_α;

2. what is the inverse function of f_α;

3. for what values of α the function f_α is increasing, and for what values it is decreasing;

4. what are the limits of f_α(x) for x→0 and for x→∞;

5. given α and β, for what x>0 you have f_α(x)>f_β(x).

--84.220.118.16 (talk) 08:22, 1 December 2009 (UTC)

steps and results of simplification

Can $x={\frac {a^{\frac {-1}{2}}}{b^{\frac {1}{2}}}}$ be simplified? ...and if so, what are the steps?

(Note that the minus sign is intentionally placed in this example, although it can be placed as a^-1/2.)

71.100.8.206 (talk) 12:51, 1 December 2009 (UTC)

$a^{-z}={\frac {1}{a^{z}}}$, so the power on the a and the power on the b are actually the same. Also, $z^{\frac {1}{2}}={\sqrt {z}}$. Most of what you can do with that expression isn't really simplification, it's just changing notation. The only simplification is observing that the powers on a and b are the same so you can rewrite it as $(ab)^{z}$. (You need to replace all the z's by the appropriate numbers.) --Tango (talk) 13:03, 1 December 2009 (UTC)

Just to be sure I have it right is it: x=(ab)^1/2 or x= 1/(ab)^1/2 due to the division of the terms in the example?

--71.100.8.206 (talk) 13:36, 1 December 2009 (UTC)

${\frac {1}{(ab)^{\frac {1}{2}}}}$. --PST 14:43, 1 December 2009 (UTC)

• Try the exponentiation article. ~~ Dr Dec (Talk) ~~ 19:04, 1 December 2009 (UTC)

• Start with $x={\frac {a^{\frac {-1}{2}}}{b^{\frac {1}{2}}}}$. Square the expression: $x^{2}={a^{-1} \over b}$. Simplify the fraction: $x^{2}={1 \over ab}$. Un-square: $x={1 \over {\sqrt {ab}}}=(ab)^{-1/2}$.

67.117.145.149 (talk) 20:58, 1 December 2009 (UTC)

You must be exceedingly careful when squaring equations, or taking the square root of both sides, because you can introduce new solutions which don't fit the original equation, or eliminate solutions which otherwise would have satisfied them. For example a=1, b=-1/2 is not a solution to $2={1/ab}$, but is a solution to $2^{2}={(1/ab)^{2}}$. Additionally, the square root sign is defined as the *positive* square root, so while $x^{2}=4$ has two solutions (x = 2 and x = -2), $x={\sqrt {4}}$ only has one (x = 2). -- 128.104.112.95 (talk) 17:47, 2 December 2009 (UTC)

Transpose

What is the meaning of transpose of an integral equation ? Thanks-Shahab (talk) 15:32, 1 December 2009 (UTC)

Talking of linear integral equations, say on $L^{2}(X)$ with a kernel $K\in L^{2}(X\times X)$, the theory is much the same as in finite dimension, due to the Fredholm index theory. Check Fredholm alternative. --pma (talk) 15:53, 1 December 2009 (UTC)

So we just consider another integral equation with K*(y,x)(if K(x,y) was the original kernel). Is that right? Is adjoint just another name.-Shahab (talk) 16:02, 1 December 2009 (UTC)

No, adjoint operators have a specific meaning. (Igny (talk) 00:51, 2 December 2009 (UTC))

Actually the adjoint of an integral operator on $L^{2}(X)$ with kernel $K(x,y)$ is the integral operator with kernel ${\overline {K(y,x)}}$. The term transpose of an operator $T:X\to Y$ is mainly used to denote the operator $T^{*}:Y^{*}\to X^{*},$ mapping the linear form $y^{*}\in Y^{*}$ into $T\circ y^{*}\in X^{*}$, that is $\langle T^{*}y^{*},x\rangle _{X}=\langle y^{*},Tx\rangle _{Y}$, where in general $\langle \cdot ,\cdot \rangle _{X}$ denotes the canonical pairing $X^{*}\times X\to \mathbb {C}$. --pma (talk) 15:18, 2 December 2009 (UTC)

Cyclic hexagon

It's easy to show that all hexagons inscribed in a circle have each pair of three alternate angles summing to 360°, but is this condition sufficient for the figure to be cyclic? As far as I can see, the example case of successive angles being 179°, 179°, 179°, 179°, 2° and 2° will indeed be cyclic, albeit looking like a very small segment of the circle. And if the condition is sufficient, what further condition would have to be put on the angles for the centre of the circle to be within the hexagon?→86.132.161.145 (talk) 20:40, 1 December 2009 (UTC)

Any two consecutive vertices can be moved independently of the others while preserving angles, so the angles do not define the hexagon up to similarity. If you start with an inscribed hexagon then you could move two vertices so they are not on the circle any more, but any three of the remaining four vertices determine the circle so you can't redraw the circle to fit the changes to the moved points. So the short answer is the condition is not sufficient. In fact, no condition involving just angles will be sufficient for a polygon with more than 4 sides.--RDBury (talk) 07:42, 2 December 2009 (UTC)

(OP)I didn't mean that any hexagon with the given angle condition was bound to be cyclic, but could a cyclic hexagon be drawn with any selection of angles meeting the condition? Thanks for the above answer, but I think it deals with the question I didn't ask.→81.147.2.186 (talk) 20:00, 2 December 2009 (UTC)

So your question is whether anything else can be said about the angles of a c.h.? —Tamfang (talk) 18:34, 8 January 2010 (UTC)

$\mathbb {Z} _{n}[x]$ in GAP

How to obtain the polynomial ring $\mathbb {Z} _{n}[x]$ in GAP? --Andreas Rejbrand (talk) 23:31, 1 December 2009 (UTC)

use PolynomialRing() - see sec 64.14 in the manual [1] Tinfoilcat (talk) 12:40, 2 December 2009 (UTC)

Can you give an example? I am new to GAP. I have learned to work with groups very well, but I find it difficult to work with rings. I have tried the following:

Z2 := CyclicGroup(2);

Z2P := PolynomialRing(Z2);

but that does not work, probably because Z2 is a group and not a ring. I have also tried

Z2 := Ring(Elements(CyclicGroup(2)));

Z2P := PolynomialRing(Z2)

which does not work either (and when I try to compute Size(Z2) I expect 2, but get an error). --Andreas Rejbrand (talk) 14:32, 2 December 2009 (UTC)

I just found [2] using my friend Google. --Andreas Rejbrand (talk) 15:09, 2 December 2009 (UTC)

Resolved

see sec 14.4 of the manual, "residue class rings" Tinfoilcat (talk) 15:13, 2 December 2009 (UTC)