What are the POSIX "mandatory utilities"?

From one of the sections that you cite:

Optional utilities that are present only on systems supporting the associated option; see Codes for information on the options in this volume of IEEE Std 1003.1-2001

The mandatory utilities are the ones that are not marked as optional.

For example basename has no annotation to indicate that it's optional, so it's mandatory. alias is annotated as UP, so it's only mandatory if an implementation claims to include the User Portability Utilities option. command is mandatory, but the -v and -V options are not unless the implementation claims to include the User Portability Utilities option.