user11609: How many knights would be necessary to mate opponent's king on large finite boards, like a billion times a billion squares?
Are they fast enough to surround the opponent's king in a constant number of times for various finite board sizes, or would you need some f(board size) of them, let's say millions for our board? Would there be a difference if attacking side could use it's king too?
It's not clear how geometry works here, but it looks like when the king starts running, it's pretty fast and only two knights are fast enough to follow it. On the other hand, knights can build setups giving additional time for some distant colleague to join slowly. We start with king in the center and knights in one corner and 50 moves rule doesn't apply...

user9192: [Not exactly an answer, but just to address the related question of an infinite board that was brought up by some answers and comments.]
Here is a proper proof that it is impossible on an infinite board, even if only the right side of the board is infinite. Assign each piece a distance that is simply the column number. Let the (opponent) king start with distance k at least 3 more than the distance of any knight. We maintain the invariant that (k−1)·2 > m+n where m,n are the two greatest distances of the knights (with m = n if there are two knights at the greatest distance). Observe that each knight move adds at most 2 to m+n. Also, if the invariant holds then there cannot be two knights that can attack the column just on the right of the king, so the king can clearly move to an unattacked square while moving rightward, preserving the invariant. Since the king can continue indefinitely, it is impossible to checkmate the king.

user15324: Not rigerous, however:

In lateral movement two knights move as fast as one king.
We know from end-game theory that two knights are not able to force the king into positions.

.. thus I'd say it's very unlikely that unlimited knights+king would be able to mate a king that has a free direction to run in (unlimited board). If it's possible to corner it however (limited board and unlimited moves), unlimited knights are certainly enough, as they could simply divide up the board and slowly decrease the available space.

user12629: I think we can at least set a maximum for the number of knights needed.
First off, the special cases. Checkmate is impossible on a 3x3 (or smaller) board. The knights cannot control the middle square and can thus never give checkmate. On a 4x4 board, the board is so small that if there are 4 knights and the king starts in the middle, the king is next to one of the knights and may be able to take it immediately and fork the remaining 3 for an easy draw, or if you move the king to the corner so it doesn't start in check, it starts the game immediately stalemated.
In the following diagram, the black pawns represent squares that the king cannot cross:
[FEN "3k4/8/8/ppp2ppp/2pppp2/NN4NN/8/8 w - - 0 1"]

If you imagine that pattern continuing, each pair of knights is controlling 6 files.  So, to make a wall covering the entire board, you would need 2 knights for every 6 files. An additional 2 knights could ensure that the wall can slowly advance with no gaps. The wall can continue to advance until the opposing king is pinned to the back rank, and after that checkmate should be easy. So, on an NxN board of size at least 5, a maximum of ceiling(N/6) * 2 + 2 knights should be enough to checkmate. On a 300x300 board, which contains 90,000 squares, 102 knights would therefore be sufficient. (This implies a maximum of 6 knights needed on a regulation 8x8 board, which I'm pretty sure is more than what is actually needed - 4 seems like it would be enough.)
There are probably better methods which could reduce this number, but I give it as a starting point.

Are they fast enough to surround opponent's king in very limited constant count for various finite board sizes

It could never be constant (and that part won't change even if the side with the knights also has a king.) After all, only 2 knights (or a king) can chase the king, and 2 knights (or a king... or even 2 knights and a king) cannot force checkmate, so at the very least the opposing king could run until it hit the edge of the board, and the amount of moves that takes is a function of the board size. Therefore, no checkmating method could be faster than O(N). The method I give of advancing a wall seems to be O(N^2) since the wall has further to go and takes longer to advance the bigger the board is.

11609: <p>How many knights would be necessary to mate opponent's king on large finite boards, like a <strong>billion times a billion squares</strong>?</p>
<p>Are they fast enough to surround the opponent's king in a <strong>constant</strong> number of times for various finite board sizes, or would you need some <strong>f(board size)</strong> of them, let's say millions for our board? Would there be a difference if attacking side could use it's king too?</p>
<p>It's not clear how geometry works here, but it looks like when the king starts running, it's pretty fast and only two knights are fast enough to follow it. On the other hand, knights can build setups giving additional time for some distant colleague to join slowly. We start with king in the center and knights in one corner and 50 moves rule doesn't apply...</p>
 9192: <p>[Not exactly an answer, but just to address the related question of an infinite board that was brought up by some answers and comments.]</p>
<p>Here is a proper proof that it is impossible on an infinite board, even if only the right side of the board is infinite. Assign each piece a distance that is simply the column number. Let the (opponent) king start with distance k at least 3 more than the distance of any knight. We maintain the invariant that (k−1)·2 &gt; m+n where m,n are the two greatest distances of the knights (with m = n if there are two knights at the greatest distance). Observe that each knight move adds at most 2 to m+n. Also, if the invariant holds then there cannot be two knights that can attack the column just on the right of the king, so the king can clearly move to an unattacked square while moving rightward, preserving the invariant. Since the king can continue indefinitely, it is impossible to checkmate the king.</p>
 15324: <p>Not rigerous, however:</p>

<ol>
<li>In lateral movement two knights move as fast as one king.</li>
<li>We know from end-game theory that two knights are not able to force the king into positions.</li>
</ol>

<p>.. thus I'd say it's very unlikely that unlimited knights+king would be able to mate a king that has a free direction to run in (unlimited board). If it's possible to corner it however (limited board and unlimited moves), unlimited knights are certainly enough, as they could simply divide up the board and slowly decrease the available space.</p>
 12629: <p>I think we can at least set a maximum for the number of knights needed.</p>

<p>First off, the special cases. Checkmate is impossible on a 3x3 (or smaller) board. The knights cannot control the middle square and can thus never give checkmate. On a 4x4 board, the board is so small that if there are 4 knights and the king starts in the middle, the king is next to one of the knights and may be able to take it immediately and fork the remaining 3 for an easy draw, or if you move the king to the corner so it doesn't start in check, it starts the game immediately stalemated.</p>

<p>In the following diagram, the black pawns represent squares that the king cannot cross:</p>

<pre><code>[FEN "3k4/8/8/ppp2ppp/2pppp2/NN4NN/8/8 w - - 0 1"]
</code></pre>

<p>If you imagine that pattern continuing, each pair of knights is controlling 6 files.  So, to make a wall covering the entire board, you would need 2 knights for every 6 files. An additional 2 knights could ensure that the wall can slowly advance with no gaps. The wall can continue to advance until the opposing king is pinned to the back rank, and after that checkmate should be easy. So, on an NxN board of size at least 5, a maximum of <code>ceiling(N/6) * 2 + 2</code> knights should be enough to checkmate. On a 300x300 board, which contains 90,000 squares, 102 knights would therefore be sufficient. (This implies a maximum of 6 knights needed on a regulation 8x8 board, which I'm pretty sure is more than what is actually needed - 4 seems like it would be enough.)</p>

<p>There are probably better methods which could reduce this number, but I give it as a starting point.</p>

<blockquote>
  <p>Are they fast enough to surround opponent's king in very limited <strong>constant</strong> count for various finite board sizes</p>
</blockquote>

<p>It could never be constant (and that part won't change even if the side with the knights also has a king.) After all, only 2 knights (or a king) can chase the king, and 2 knights (or a king... or even 2 knights <em>and</em> a king) cannot force checkmate, so at the very least the opposing king could run until it hit the edge of the board, and the amount of moves that takes is a function of the board size. Therefore, no checkmating method could be faster than O(N). The method I give of advancing a wall seems to be O(N^2) since the wall has further to go and takes longer to advance the bigger the board is.</p>
