23,058 reputation
270137
bio website
location
age
visits member for 5 years, 2 months
seen 18 hours ago

If I like your problem, I'll think of it in honest. However, if the question is badly posed or the information is incomplete, I'll vote to close it when in a bad mood and waste several hours of your and my time asking for clarification, pointing out trivial counterexamples, etc., when in a good mood. In both cases, the most likely outcome is that I'll finally switch my attention to something else. ;)


18h
comment Connected components $0-1$ matrices
First, you can enhance the probabilistic argument by tweaking the parameters. Let $p$ be the probability of $1$ in every cell. Then the probability of no isolated $1$ is $[(1-p(1-p)^8]^{n^2/9}$, which, for $p=1/9$ is less than $1/(n!)^2$ for $n\approx 3000$ already (not small yet, but somewhat better than $96462$). Second, you can change the way you place 1's from totally random to semi-deterministic, which, if executed intelligently, may shave off another factor of 10. At last, you can use computers to check sizes up to 8 or so (16 or so, if you spend some time on the algorithm design first).
18h
comment Connected components $0-1$ matrices
@Christian Remling Not in the slightest :-)) (wide grin). As to the first part, that is indeed an issue with all of us sometimes. Once the question is resolved as posed, let's see what is the simplest and clearest explicit construction we can come with. I'm as eager as The Masked Avenger to see it though I have no time to think of it myself at the moment.
22h
comment Connected components $0-1$ matrices
@Turbo I have already explained how it ended as a comment ;-). Also, it is neither "my" (I wish I were 1/10000000 as brilliant as Paul Erdos), nor "idea" (the proof is complete, though the exposition may be somewhat terse). However I promise that if I find an explicit example before anybody else, I'll post it as an answer :-)
23h
comment Connected components $0-1$ matrices
@Turbo We also have to take care of various possibilities of Mi that could make different matrices M ... Counting may give hints but unless lucky not a proof. Erm... What do you mean by that? Independent events remain independent regardless of the order in which you list them!
23h
comment Connected components $0-1$ matrices
@The Masked Avenger I am hopeful for an explicit matrix of size 10 by 10 or smaller of at least 2 components. That can be easily done on a computer (at some point such matrices become an overwhelming majority). However, if the sentence is intended to mean "An explicit construction (nevermind the size) with a clear reason for impossibility", I concur :-).
23h
comment Connected components $0-1$ matrices
@Christian Remling it's not what most of us would try first here Why??? Isn't "If you have no idea what to do, just do a random thing" as basic as "Eye for eye and tooth for tooth"? (at least, 50 or so years after Erdos demonstrated the efficacy of this principle in mathematics) :-). But, indeed, random graphs, random constructions, random sampling, etc. are beautiful and permeate all areas of modern science. Hail the fair Tyche! Coming back to Earth, I thought of posting it as an answer but then decided on a comment after seeing "Why is it on hold?" . Too late to change now.
1d
comment Conceptual explanation of Strassen's trick for matrix multiplication
Denis, I remember that there was some pretty famous paper (quite hard to read for a normal human though) where this concept was if not introduced, then thoroughly discussed for the first time with fast matrix multiplication as one of main motivations. I vaguely remember the content but nothing else except that one of the reviews was "every mathematician should read this one". Do you know the reference?
1d
comment Connected components $0-1$ matrices
@The Masked Avenger Given that you claim a positive answer, it looks like we interpret the problem slightly differently again (just saying this in case one of us gets puzzled by the other's words :-) )
1d
comment Connected components $0-1$ matrices
The answer is "No". Take a random size $n$ matrix with each entry being $1$ with probability $1/2$. Then the probability that we don't have any isolated $1$ is about $e^{-cn^2}$. The permutations are just $e^{Cn\log n}$, which (outside the state of Kansas) is a slower growing function. An old trick, of course, but still useful :-)
1d
reviewed Leave Open Open problems in compressed sensing
1d
reviewed Leave Open Roots in the solution
1d
comment Sets of squares representing all squares up to $n^2$
Another simple way to see it is to note that $2^{2n}=(2^{n})^2$ and $2^{2n+1}=(3\cdot 2^{n-1})^2-(2^{n-1})^2$. Since every number has a binary decomposition, $1+(-1)=0$, and no square contains a single $2$ in it, we are almost done with the only problem that we may have some nasty effect near the endpoint (we cannot use numbers greater than $N$ to represent the squares near $N^2$). However, if we have $m^2>N^2/2$, then we can use the binary representation of $N^2-m^2$ or $(N-1)^2-m^2$ (whichever is even to avoid $2$ in the decomposition) instead because $\frac 98\cdot \frac 12<1$.
1d
comment Open problems in compressed sensing
This is not a sure finalist for the best question ever competition, of course, but why to downvote (especially without any explanation of what exactly you dislike)????
1d
comment Conjecture on maximum of symmetric combinatoric function
@NicoDean As to the magic, one thing that I enjoy most is seeing how people perceive the "routine" and "ordinary" things as incredible insights and inventions, which they, indeed, were at the moments they came into existence, and what makes me most gloomy and sarcastic is to see the opposite perception, which, alas, seems to be way more widespread. So, thank you! :-)
1d
comment Conjecture on maximum of symmetric combinatoric function
@NicoDean Are these standard-tricks and you saw them rather early, or did you need to fiddle around a lot? I certainly needed to "fiddle around" a bit, as you can see from my comments and the timestamps on my posts, though the Cauchy-Gram trick and the Cauchy inequality are totally standard for any undergraduate student who took a decent course in linear algebra in Euclidean spaces and were there from the very beginning.
2d
comment this sequence $A_{n}$ have recursive relations?
+1 for bringing people's attention to that brilliant (though, alas, so far totally useless for my favorite kind of "formal algebra" questions) text again.
2d
comment how to efficiently compute the mean function for non-homogeneous poisson process?
So, what exactly is the setup? Are you given some crazy oscillatory formula for $\lambda(t)$ (then what is it?) or something else? I still have no idea what the conditions of your problem are.
2d
comment how to efficiently compute the mean function for non-homogeneous poisson process?
"Suppose that I know all intensity functions lambda(t)"+", m(t) in the integral of lambda(t) from 0 to t"+"Is there an efficient algorithm to compute m(t)?"="Is there an efficient way to compute a definite integral over an interval?". Am I misunderstanding something?
2d
revised Conjecture on maximum of symmetric combinatoric function
added 8 characters in body
2d
comment Conjecture on maximum of symmetric combinatoric function
@NicoDean Done. I also switched from pseudo-code to assembler and split the argument into small elementary morsels to digest (or to refer to if you have additional questions) :-)