I was wondering which that inventive method is

Switching to printf is far more than 4 characters.

print("$line_num $rest\n");
printf("%03d %s\n", $line_num, $rest);
                           12345678901
[download]

Maybe he's referring to string autoincrement.

If you start with

$ perl -e'my $i=0; while (<>) { print ++$i, " $_" }' file
1 foo
2 bar
3 baz
4 qux
[download]

then this is just four more characters:

                1 234
$ perl -e'my $i="000"; while (<>) { print ++$i, " $_" }' file
001 foo
002 bar
003 baz
004 qux
[download]

(Note that the trick will fail if you use $i as an number.)

I would have started with

$ perl -e'while (<>) { print "$. $_" }' file
1 foo
2 bar
3 baz
4 qux
[download]

so I would have had to add far more characters than four. In fact, using printf is still shorter:

$ perl -e'while (<>) { printf "%03d %s", $.,  $_ }' file
001 foo
002 bar
003 baz
004 qux
[download]

(Avoiding -p and -l since this is suppose to be part of a larger program.)