Is the PID of a child process always greater than the PID of its parent on Linux?
No, for the very simple reason that there is a maximum numerical value the PID can have. If a process has the highest PID, no child it forks can have a greater PID. The alternative to giving the child a lower PID would be to fail the fork() altogether, which wouldn't be very productive.
The PIDs are allocated in order, and after the highest one is used, the system wraps around to reusing the (free) lower ones, so you can get lower PIDs for a child in other cases too.
The default maximum PID on my system (/proc/sys/kernel/pid_max) is just 32768, so it's not hard to reach the condition where the wraparound happens.
$ echo $$
27468
$ bash -c 'echo $$'
1296
$ bash -c 'echo $$'
1297
If your system were to allocate PIDs randomly (like OpenBSD appears to do) instead of consecutively (like Linux), there would be two options. Either the random choice was made over the whole space of possible PIDs, in which case it would be obvious that a child's PID can be lower than the parent's. Or, the child's PID would be chosen by random from the values greater than the parent's PID, which would on average put it halfway between the parent's PID and the maximum. Processes forking recursively would then quickly reach the maximum and we'd be at the same point as mentioned above: a new fork would need to use a lower PID to succeed.
Also there exists the potential for security vulnerabilities using kernel notifications and forking yourself to avoid detection by a process table scan; this if done right results in your process having a lower PID and process tools not seeing the process in question.
http://cve.circl.lu/cve/CVE-2018-1121
procps-ng, procps is vulnerable to a process hiding through race condition. Since the kernel's proc_pid_readdir() returns PID entries in ascending numeric order, a process occupying a high PID can use inotify events to determine when the process list is being scanned, and fork/exec to obtain a lower PID, thus avoiding enumeration. An unprivileged attacker can hide a process from procps-ng's utilities by exploiting a race condition in reading /proc/PID entries. This vulnerability affects procps and procps-ng up to version 3.3.15, newer versions might be affected also.