How should I express theorems without a proof in a research paper?

What do you do when you have a conjecture, and you run experiments that confirm your conjecture, but you are unable to provide a formal proof (perhaps because it's too complicated)? Do you name them as conjectures or observations or... what?

This is in the context of a CS theory paper.

• It's still a conjecture, now with some supporting evidence. Nov 10 '14 at 5:33
• A theorem without a proof is not a theorem. Nov 10 '14 at 7:23
• @JessicaB: Any theorem that is literally without a proof is a monkey. Vacuously, that is. Sep 4 '17 at 11:19

In mathematics and TCS (which is really a branch of mathematics), if you don't have a proof, you don't have a theorem. (You write "experiments", which I will assume means "computer calculations". Please let me know if this is not the case.) Doing some computer calculations can be interesting and even sometimes publishable, but it does not constitute any kind of proof, formal or otherwise. (Added: Well, unless it does, of course. You can prove a theorem by reducing it to a finite calculation and doing that calculation by hand or by computer or some of both. You can't prove a theorem which pertains to infinitely many cases by doing finitely many of them and claiming "and so on".) Also, although the word "confirm" is often used in this way in empirical science, in mathematics to "confirm a conjecture" means to prove it.

I see two possible questions here:

1. How do I write up computational evidence for a result that I cannot prove in a paper?
2. Can I publish a paper in which I do not prove my conjecture but only have computational evidence towards it?

The first question is more straightforward. You state the conjecture -- i.e., the statement that you think is a theorem but can't yet prove. Some discussion of the provenance of the conjecture is probably a good idea but is not strictly necessary. However, if you got the conjecture from somewhere else you must indicate that. Then you document the calculations you made. Finally, you probably want to make some remarks about why the calculations make you confident in your conjecture (if that is the case). Here sometimes informal reasoning can be helpful: e.g. if your conjecture is that for two sequences of integers a_n and b_n that a_n and b_n are always congruent modulo 691, then if you check this for the first 100,000 terms then in some naive sense the probability that this happened by accident is (1/691)^{100,000}, which is vanishingly small.

The second question is much more complicated. It can be hard to publish papers in which you do not prove a theorem but "only" give computer evidence...but not as hard as it used to be. Mathematics is slowly becoming more enlightened about the merits of computer calculations. I would say though that you need to understand the field much better to be able to predict whether a paper primarily containing computations would be publishable than to publish a more "theoretical" paper: many, many referees and journals will say "no theorem, no proof, no paper", so you should expect to work much harder to sell your work.

• Well, the problem is simply too complicated, and yes, by experiments I meant computational experiments. I have been working on this problem for over 3 months now, and I am hoping to raise some discussion on the topic and perhaps even initiate some collaboration that hopefully leads to an enhanced theoretical understanding of the problem.
– NeoN
Nov 9 '14 at 22:44
• "Well, the problem is simply too complicated" I'm not scolding you for not being able to prove the conjecture! Every mathematician I know has conjectures they would like to prove but can't. That's almost the definition of a mathematician.... Nov 9 '14 at 22:46
• Good point! this is perhaps the first time I've encountered a conjecture that I haven't been able to solve after a few months. I guess, this is the beauty of Math!
– NeoN
Nov 9 '14 at 22:49
• @NeoN 3 months is not a long time to work on a reasonably complex mathematical problem. Nov 10 '14 at 13:29

The important thing is to be honest and clear. In any proof-oriented subject (including theoretical CS), you should carefully distinguish theorems you have proved from conjectures you believe but have not proved. It's reasonable to give evidence in favor of your conjectures (such as your experiments) or to discuss possible proof techniques that might work, as long as you are clear about what you have or haven't done.

What makes this awkward is that sometimes beginners are tempted to be a little unclear in dishonest ways. Suppose there's something you are pretty sure you could do if you had more time, and it's embarrassing to admit that you haven't yet been able to work out the details. It can be tempting to write something vague like "These techniques apply to case X as well" and rationalize it by saying it's not technically a lie, since you never actually said you applied them to complete the proof. Nevertheless, it's unethical since it misleads readers into thinking you've done more than you have.

Even if you don't feel this temptation yourself, it's important to avoid even the appearance of impropriety, so it's best to be extra careful about anything near the borderline of what you have or haven't proved.

Do you name them as conjectures or observations or what?

Conjecture sounds like the appropriate name here. Observation might make sense if this terminology is commonly used in your subfield, but it sounds potentially problematic to me. It sounds a little too much like something you could prove but are omitting the details for, rather than something you have been unable to prove (so if you use that terminology, you should be careful to make this clear).