Weird Sums

[Dragonfall]

Main Question or Discussion Point

I'd like to see whether weird reciprocal sums of integers in the form $$\sum_{x\in S}\frac{1}{x}$$, where S is some unconventional set of integers, converges or diverge. Does anyone know any?

For example, $$\sum_{x\in S}\frac{1}{x}$$ where S is the set of integers that, when expanded in binary, represents a valid Java program compiled on the x86 architecture. Is it convergent? Divergent?

 

[Santa1]

To answer your second question, would'nt you consider 0 an integer?

edit: Well in that case if S is symmetric about 0 you also see something interesting happening. But with 1/x as a summand the sum is usually divergent.

 

[Dragonfall]

I suppose we'll have to remove 0 from the sets.

 

[Vid]

The set of binary numbers would have to be finite so convergence or divergence isn't really a question. If the set is infinite, it depends on the set. The set of all squares is convergent, but the set of all even numbers is divergent.

 

[uman]

"A valid Java program compiled on the x86 architecture" is meaningless.

"A valid program compiled for the Java VM" might not be.

 

[Dragonfall]

"A valid Java program compiled on the x86 architecture" is meaningless.

"A valid program compiled for the Java VM" might not be.

Well then let's go with "a valid program compiled for the java VM". Does it converge?

The set of binary numbers would have to be finite so convergence or divergence isn't really a question.

The set of integers is not finite, expressed in binary or otherwise.

 

[Vid]

I meant a set of binary numbers representing a program would have to be finite.

 

[uman]

But the set of all integers representing a program isn't...

 

[Dragonfall]

I meant a set of binary numbers representing a program would have to be finite.

Like Uman said, the set of all binary numbers which represent a program is not finite.

 

[indrifan]

Here's a 'top of the head' answer - I haven't actually worked it out. But I suspect the java example converges (edit - diverges). Here's my thinking: the simplest valid java program would just be some declaration of a constant (say a string), along with a bit of overhead. So there would be a sequence of valid programs where the constant value increases by 1 in the coding representation. The question is, what happens when a new byte needs to be added? Can we always get away with just adding one more byte to the binary (I don't know enough about java byte-coding to wnaswer that). Is it ever the case where the consecutive gaps between valid programs are large enough that the sum of their inverses converge? I strongly suspect the answer is no, but I don't have time right now to work out the details. If someone else doesn't beat me to it, maybe I'll work through it this weekend.

edit - oops. I meant to say diverges.

 

[Dragonfall]

It depends on how Java "enumerates" programs. Two different enumerations of Turing machines, for example, might give a convergent and a divergent sum. For example, in one enumeration all valid programs are enumerated at powers of 2, and in the other it's the opposite.

EDIT: In fact, I think the Java example diverges. Any set containing an infinite arithmetic progression leads to a divergent sum, and maybe that Java binaries set contains such a sequence.

 

[indrifan]

It depends on how Java "enumerates" programs. Two different enumerations of Turing machines, for example, might give a convergent and a divergent sum. For example, in one enumeration all valid programs are enumerated at powers of 2, and in the other it's the opposite.

Yes. But I'd be very surprised if the java byte-code compiler used any kind of sparse coding, much less exponential. I think it's much more likely that it's going to be linear, so S will look a lot more like {x: x=m + 1} for some minimum m chars of overhead.

If we were talking about Godel-numbering, or some such scheme, then the "weird set" will almost certainly converge. But that's because Godel numbers are constructed so as to have lots of desirable properties when considered "all at once", as a number. There's no need for the Java VM to consider programs in that way - so it will fill the "valid program space" much more efficiently, i.e. much more densely.

 

[indrifan]

@Dragonfall, I posted while you were editing. Sounds like we're in agreement.

I'm not sure my last post was actually coherent - but I hope my point gets across.
What I'm trying to say is that, in order to find a set you're talking about that converges, you'll have to find some set S that "grows fast". One potentially interesting example that springs to my mind is Ramsey numbers.

 

[Vid]

Oh, I thought we were taking the binary from a JAVA program and creating a set of integers from that. Not the set of integers that could represent any JAVA program. My bad.

 

[Dragonfall]

Ok what about this, the set of perfect numbers? You don't have to solve the question of whether there are infinitely many, since you can show (somehow) that the sum is finite (or even rational), a la Brun's constant.